本文共 1594 字，大约阅读时间需要 5 分钟。

问题：

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

先二分查找，再前后搜索。

注意边界条件，如果搜索到头尾该怎么办。

代码：

class Solution {public:    vector
   
     searchRange(int A[], int n, int target) {        int result,i;        vector
    
      re_list;        result = b_search(A, n, target);        if(result == -1)        {            re_list.push_back(result);            re_list.push_back(result);        }        else        {            i = result;            while(i >= 0)            {                if((i-1)<0 ||(A[i-1] != A[i]))				{                    re_list.push_back(i);					break;				}                else                    --i;            }			i = result;            while(i <= n-1)            {                if((i+1)>=n || A[i+1] != A[i])                {					re_list.push_back(i);					break;				}                else                    ++i;            }        }		return re_list;    }    int b_search(int A[], int n, int target)    {        int start,end,mid;        start = 0;        end = n-1;        while(start <= end)        {            mid = start+(end-start)/2;            if(A[mid] == target)            {                return mid;            }            if(A[mid] < target)            {                start = mid+1;            }            else            {                end = mid-1;            }        }        return -1;    }};
    
   

转载地址：http://oktsi.baihongyu.com/