题解 | #二分查找-II#
二分查找-II
http://www.nowcoder.com/practice/4f470d1d3b734f8aaf2afb014185b395
复习二分搜索算法的不变性和单调性,根据题目设置不同的不变性和单调性
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* 如果目标值存在返回下标,否则返回 -1
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int search(vector<int>& nums, int target) {
// write code here
int s = nums.size();
int lo = 0;
int hi = s;
int m = (lo + hi) / 2;
if(nums.size() == 0){
return -1;
}
while(lo < hi){
if(nums[m] >= target){
hi = m;
}else{
lo = m + 1;
}
m = (lo + hi) / 2;
}
if(nums[lo] > target){
return -1;
}
else{
return lo;
}
}
};