题目
Given an array of integers sorted in ascending order, 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，-1）
由于时间需要O(log n)，所以需要使用二分查找，直到找到特定值，然后再周围搜索所有等于该值的位置，如果没有直接返回-1.
C代码如下，已通过。
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int p=0,q=numsSize-1;
int *ans=(int *)malloc(2*sizeof(int));
while(p<q)
{
if(nums[(p+q)/2] > target) q = (p+q)/2-1;
else if(nums[(p+q)/2] < target) p = (p+q)/2+1;
else break;
// printf("%d %d\n",p,q);
}
if(p>q||(p==q&&nums[p]!=target))
{
ans[0]=-1;
ans[1]=-1;
*returnSize=2;
}
else
{
p=(p+q)/2;
q=p;
while(p>0)
{
if(nums[p]==nums[p-1]) p--;
else break;
}
while(q<numsSize-1)
{
if(nums[q]==nums[q+1])q++;
else break;
}
ans[0]=p;
ans[1]=q;
*returnSize=2;
}
return ans;
}
