[笔记]二分查找的几种写法
程序员文章站
2024-03-20 10:21:04
...
基本形式
-
left
和right
均为索引值 - 循环条件:
left <= right
- 向左查找:
right = mid-1
- 向右查找:
left = mid+1
- 查找条件可以在不与元素的两侧进行比较的情况下确定
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
// End Condition: left > right
return -1;
}
需要访问右邻居
- 初始条件:
left
为索引值,right
为索引值+1
- 循环条件:
left < right
- 向左查找:
right = mid
- 向右查找:
left = mid+1
- 可以访问右邻居
mid+1
,因为查找空间在每一步中至少有2个元素 - 需要进行后处理。当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size();
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.size() && nums[left] == target) return left;
return -1;
}
需要访问左右邻居
- 初始条件:
left
和right
均为索引值 - 循环条件:
left + 1 < right
- 向左查找:
right = mid
- 向右查找:
left = mid
- 可以访问左右邻居,因为查找空间在每一步中至少有3个元素
- 需要进行后处理。当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。
int binarySearch(vector<int>& nums, int target){
if (nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
C++中的二分查找
std::lower_bound(arr.begin(), arr.end(), target)
返回首个不小于target的元素的迭代器std::upper_bound(arr.begin(), arr.end(), target)
返回首个大于target的元素的迭代器
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
auto lower = std::lower_bound(data.begin(), data.end(), 4);
auto upper = std::upper_bound(data.begin(), data.end(), 4);
std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " ")); // 4 4 4
}