Search for a Range

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

 

 

 

1 class Solution { 2 public: 3     vector
      
        searchRange(int A[], int n, int target) { 4         5   6         vector
       
        res(2);           7   8         res[0]=bs(A,n,target-1)+1; 9         res[1]=bs(A,n,target);        10   11         if(res[1]==-1||A[res[1]]!=target)12         {13             res[0]=-1;14             res[1]=-1;15         }          16         return res;17     }18    19     //通过这个二分查找，如果有多个target的话可以找到最靠右边的元素20     //同时也得注意，如果没有target则找到的是比target小的最大的最靠右元素21      int bs(int A[],int n,int target)22     {23         int left=0;24         int right=n-1;25         int mid=(left+right)/2;26         int ret=-1;27        28         while(left<=right)29         {30             if(A[mid]>target)31             {32                 right=mid-1;33             }34             else35             {36                 //只要是当前元素小于等于target，left就会右移，因此找到最靠右的元素37                 ret=mid;38                 left=mid+1;39             }40             mid=(left+right)/2;41         }          42         return ret;43     }44    45 };