详解二分法查找目标值/二分法查找上下界的两种写法

本文主要是介绍详解二分法查找目标值/二分法查找上下界的两种写法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文中默认数组呈升序。

💡 绝对不能使用left = cur这种更新，由于整数除法取下界，left不更新会导致循环无法结束

寻找与target相等

1. 可以用(l < r)写法，末尾r==l需要检查是否满足条件，满足则输出，不满足则输出-1
2. 可以用(l<=r) 写法，末尾输出r 不需要检查是否满足条件，不满足的情况下r为-1，因此结果r可能会超出数组索引，注意不要对此进行nums[r]的检查

// ==
// Method1 : left=mid+1, right=mid, 此时最优解为最后的重合解（若可行）
// 遍历直至left = right，左右重合时退出循环，此时重合解若可行，即为答案
int BinSearch1(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l < r) {mid = (l+r)/2;if (nums[mid] == target)return mid;else if (nums[mid] < target) {l = mid + 1;}elser = mid;}if (nums[r] == target)return r;return -1;
}// ==
// Method2 : left=mid+1, right=mid-1, 此时最优解需要另外记录
// 遍历直至left > right，左右重合时仍然进入循环并进行结果记录
int BinSearch2(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l <= r) {mid = (l+r)/2;if (nums[mid] == target)return mid;else if (nums[mid] < target) {l = mid + 1;}elser = mid - 1;}return r;
}

寻找第一个小于（等于）target

💡 需要使用(l<=r) 的写法

因为查找≤时不满足条件更新的是右界，满足条件下更新左界；

如果采用(l<r)写法：

• 更新左界如果使用l = mid+1 ，由于mid此时满足条件，会导致新区间错失满足条件的点，答案错误
• 如果使用l=mid，由于mid=(l+r)/2整数除法取下界，某些情况下左界会不更新，从而引起循环无法结束，程序错误

综上，在升序区间查找≤时只能采用(l≤r) 的写法，并通过r输出最终结果：若无满足条件的元素，将会使得r==-1 。

// <
int BinLBound(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l <= r) {mid = (l+r)/2;// 先更新不满足条件if (nums[mid] >= target) {r = mid - 1;}elsel = mid + 1;}return r;
}// <=
int BinLEBound(vector<int> nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l <= r) {mid = (l+r)/2;if (nums[mid] > target)r = mid - 1;elsel = mid + 1;}return r;
}

寻找第一个大于（等于）target

1. 可以用(l<r)
2. 可以用(l<=r)

// >
int BinHBound(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l < r) {mid = (l+r)/2;if (nums[mid] <= target)l = mid + 1;elser = mid;}if (nums[r] > target)return r;return -1;
}
// >=
int BinHEBound(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l < r) {mid = (l+r)/2;if (nums[mid] < target)l = mid + 1;elser = mid;}if (nums[r] >= target)return r;return -1;
}

整体测试代码

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> nums{-5, 0, 1, 2, 5, 10, 30, 90};int target = 90;cout << BinSearch1(nums, target) << " " << BinSearch2(nums, target) << endl;cout << BinLBound(nums, target)  << " " << BinLEBound(nums, target) << endl;cout << BinHBound(nums, target)  << " " << BinHEBound(nums, target);return 0;
}

这篇关于详解二分法查找目标值/二分法查找上下界的两种写法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---