二分查找
-
原理
> 给定某一数组,数组的前一半或者后一半满足某一性质,比如说数组“nums = {1, 2, 3, 4, 5}”中,nums[0: 2]是满足小于等于3的,而另一半则不满足,我们则可以利用二分查找来找到nums[2]这个位置。反之nums[2:4]都是满足大于等于3的,我们也可以利用二分查找找到nums[2]这个位置。 -
总结
> 给定某一个数组,数组的左子数组或右子数组满足某个性质,我们利用二分查找找到满足这一性质的左子数组的最后一个数的位置,或者是满足这一性质的右子数组的最前一个数的位置
模板
// nums升序排列,查找大于等于target的第一个数
int binary_search1(vector<int> &nums, int target){
int l = 0, r = nums.size() - 1; // 查找的范围
while(l < r){
int mid = (l + r) / 2;
if(nums[mid] >= target) r = mid; // nums[mid]满足这一性质,答案在mid或者mid前面
else l = mid + 1; // 不满足,则前面的数都不满足。
}
return l; // 大于等于target的第一个数的位置就是l或者r
}
// nums升序排列,查找小于target的第一个数
int binary_search2(vector<int> &nums, int target){
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = (l + r + 1) / 2; // 注意这里,如果下一行是l = mid 则括号里面要+1
if(nums[mid] < target) l = mid;
else r = mid - 1;
}
return l;
}