【leetcode】Search for a Range（middle）

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

思路：

我自己用了个最简单的，普通的二分查找，然后两边延伸找起始和结束点。

int *searchRange(int A[], int n, int target) {

    int ans[] = {-, -};

    int l = , r = n - ;

    while(l <= r)

    {

        int m = (l + r) / ;

        if(A[m] == target)

        {

            ans[] = ans[] = m;

            while(ans[] -  >=  && A[ans[]] == A[ans[] - ]) ans[]--;

            while(ans[] +  < n && A[ans[]] == A[ans[] + ]) ans[]++;

            return ans;

        }

        else if(A[m] > target)

            r = m - ;

        else

            l = m + ;

    }

    return ans;

}

大神分成了分别用两次二分查找找起始和结束位置

https://leetcode.com/discuss/18242/clean-iterative-solution-binary-searches-with-explanation中有详细解释

vector<int> searchRange(int A[], int n, int target) {

    int i = , j = n - ;

    vector<int> ret(, -);

    // Search for the left one

    while (i < j)

    {

        int mid = (i + j) /;

        if (A[mid] < target) i = mid + ;

        else j = mid;

    }

    if (A[i]!=target) return ret;

    else ret[] = i;

    // Search for the right one

    j = n-;  // We don't have to set i to 0 the second time.

    while (i < j)

    {

        int mid = (i + j) / + ;   // Make mid biased to the right

        if (A[mid] > target) j = mid - ;

        else i = mid;               // So that this won't make the search range stuck.

    }

    ret[] = j;

    return ret;

}

另一种通过加减0.5来找位置的方法

class Solution:

# @param A, a list of integers

# @param target, an integer to be searched

# @return a list of length 2, [index1, index2]

def searchRange(self, arr, target):

    start = self.binary_search(arr, target-0.5)

    if arr[start] != target:

        return [-1, -1]

    arr.append(0)

    end = self.binary_search(arr, target+0.5)-1

    return [start, end]

def binary_search(self, arr, target):

    start, end = 0, len(arr)-1

    while start < end:

        mid = (start+end)//2

        if target < arr[mid]:

            end = mid

        else:

            start = mid+1

    return start

巴特西

【leetcode】Search for a Range（middle）

最新文章

热门文章