34. 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 ofO(logn).

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）在给定的数组中查找给定值，如果给定值存在，则返回第一次出现的位置；否则返回－1.

2）若返回－1，则返回起始和终止都为－1的数组；否则，分别前向和后向查找起始和终止位置，返回起始终止位置数组。


查找指定值使用递归进行查找。

1）如果下标中间值和起始下标和终止下标一致，且当前值不是指定值，则返回－1.

2）如果找到指定值则返回下标，否则，返回－1


intfindIndex(int*nums,intbegin,intend,inttarget){intlow=begin;inthigh=end;intmid=(low+high)/2;intvalue=-1;/*5778810*/if(mid==high&&low==mid&&*(nums+mid)!=target){return-1;}if(*(nums+mid)<target){value=findIndex(nums,mid+1,high,target);}elseif(*(nums+mid)>target){value=findIndex(nums,low,mid,target);}elseif(*(nums+mid)==target){returnmid;}returnvalue;}/***Returnanarrayofsize*returnSize.*Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*searchRange(int*nums,intnumsSize,inttarget,int*returnSize){int*dest=NULL;dest=(int*)malloc(sizeof(int)*3);if(!dest){returnNULL;}intmid=findIndex(nums,0,numsSize-1,target);if(mid==-1){dest[0]=-1;dest[1]=-1;dest[2]='\0';*returnSize=2;returndest;}intcnt=mid;while(cnt>=0&&*(nums+cnt)==target){cnt-=1;}intindex=mid;while(index<numsSize&&*(nums+index)==target){index+=1;}dest[0]=cnt+1;dest[1]=index-1;dest[2]='\0';*returnSize=2;returndest;}