问题叙述性说明：

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 ofO(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].

基本思路：

此题能够用二分查找法解决。

假设数组中没有target，能够在O（lgn）时间完毕。

假设数组中有target，当发现target后，对前后的内容继续用二分法 查找这种位置pos 。

1. 前面的pos须要满足 A[pos] < target && A[pos+1] == target. pos+1即是開始位置。
2. 后面的pos须要满足 A[pos] > target && A[pos-1] == target . pos-1是结束位置。

代码：

vector
     
       searchRange(int A[], int n, int target) {   //C++        vector
      
        result(2);                int low = 0, high = n-1;        int mid, begin = -1, end = -1;        while(low <= high)        {            mid = (low+high)/2;            if(A[mid] > target)                high = mid - 1;            else if(A[mid] < target)                low = mid + 1;            else             {                    begin = mid;                    end = mid;                                        //get begin                    if(low <= begin -1){                        while((low <= begin-1) && !(A[low]
       
        = end+1){                        while((high >= end+1) &&!(A[high]>target && A[high-1] == target))                        {                            mid = (high + end +1)/2;                            if(A[mid] > target)                                high = mid - 1;                            else end = mid;                        }                        if(A[high]>target && A[high-1] == target)                            end = high - 1;                    }                    break;                                }        }        result[0] = begin;        result[1] = end;        return result;    }
       
      
     

版权声明：本文博主原创文章，博客，未经同意不得转载。