给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。 如:在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2。 思路:二分查找是基本功,可以写迭代也可以写while循环,目前还是习惯写while循环一些,但是这里的要求和一般的二分查找还不太一样,主要的原因是题目要求查找出第一个,也就是即使找到了一个,也不能立即返回,需要找到第一个才行,我想了一下,有一个思路:找到了把结果赋值给一个变量,然后end更新为mid-1(因为第一个肯定比这个索引小,如果存在的话),一直把所有的二分查找都找完,返回最新的一个查找的结果就是要求的第一个的索引:
int binarySearch(vector<int> &array, int target) {
auto beg=array.begin();
auto end=array.end()-1;
int res=-1; //如果这个res最后还是-1的话,就说明没有找到。
while(beg<=end)
{
auto mid=beg+(end-beg)/2;
if(*mid==target)
{
res=mid-array.begin(); //这里是找到了,但不能保证是第一个
end=mid-1; //mid仍然更新。
}
if(*mid<target)
beg=mid+1;
if(*mid>target)
end=mid-1;
}
if(res!=-1)
return res;
// write your code here
return -1;
}