題目
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].
分析
給定一個排序數(shù)組，尋找一個給定值的開始位置和結束位置姨蟋，如果沒有該值，返回（-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;
}
