给定一个排序的整数数组(升序)和一个要查找的整数target
,用O(logn)
的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1
。
样例
在数组 [1, 2, 3, 3, 4, 5, 10]
中二分查找3
,返回2
。
给一个real耿直的解法
1 int binarySearch(vector &array, int target) { 2 // write your code here 3 int left=0,right=array.size()-1; 4 int mid; 5 while(left<=right){ 6 mid=left+(right-left)/2; 7 if(target>array[mid]){ 8 left=mid+1; 9 }10 else if(target
第一个else里面是处理几乎快找到解的时候(二分不下去了)会发生的各种情况
1、mid无法取到0或者最后
2、mid是对应target但是不是第一个出现的target