题解 | #二分查找-II#

算法思想：设置 low 和 high 两个指针，mid每次指向区间中间的元素，即 mid = low+(low+high)/2 ( 这里采用此形式而不是使用 mid=(low+high)/2 ，是为了防止 int 型数据的溢出)，如果 mid 所指的值大于 target，则在左半区间[low,mid-1]查找；如果 mid 所指的值小于 target，则在右半区间查找[mid+1,high]。与无重复有序数组二分查找要求所不同的是，找到 target 还要保证是第一个target，一个思路是找到 target后继续向前搜索，前一个值如果依然和 target 值相等，继续向前搜索，直到不相等为止。

C语言实现：

int search(int* nums, int numsLen, int target ) {
	int low=0,high=numsLen-1;
	int mid;
	while(low<=high){
		mid=low+(high-low)/2;
		if(nums[mid]==target) {//找到后继续向前检查是否为第一个目标值 
			int test=mid-1;//向前探测指针 
			while(test>=0&&nums[test]==target) test--;//和 target 值相等，继续向前搜索
			mid=test+1;//定位到第一个target
			return mid;//返回target在数组中的下标
		}
		else if(nums[mid]<target) low=mid+1;//右半区间查找
		else  high=mid-1;	//左半区间查找
	}
	return -1;
}