【算法——二分查找】
理论基础：
程序员面试经典题，二分搜索一个区间，区间查找 (LeetCode 34)_哔哩哔哩_bilibili
手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili
这个是红蓝法，很牛：二分查找为什么总是写错？_哔哩哔哩_bilibili
在二分查找中，计算中间位置使用mid = left + (right - left) / 2而不是mid = (left + right) / 2主要是为了避免整数溢出的问题。
此类型题目多样总结：
34. 在排序数组中查找元素的第一个和最后一个位置
因为二分无法查到起止位置；所以用两次二分，一次左边界，一次右边界；
会不会漏查问题：比如left左边会不会还有target
#include<iostream>
using namespace std;
#include<vector>
int main()
{
vector<int>nums = { 2,2 };
int target = 3;
int l = -1, r = nums.size();
while (l + 1 != r) //找第一个target
{
int m = l + (r - l) / 2;
if (nums[m] < target) l = m;
else r = m;
}
if (r >= nums.size() || nums[r] != target) return -1;
cout << "l:" << l << " r:" << r << endl; //r就是第一个target
l = -1; r = nums.size();
while (l + 1 != r) //找最后一个target
{
int m = l + (r - l) / 2;
if (nums[m] <= target) l = m;
else r = m;
}
cout << "l:" << l << " r:" << r << endl; //l就是最后一个target
return 0;
}35. 搜索插入位置
#include<iostream>
using namespace std;
#include<vector>
int main()
{
vector<int>nums = { 1,3,5,6 };
int l = -1, r = nums.size();
int target = 7;
while (l + 1 != r)
{
int m = l + (r - l) / 2;
if (nums[m] >= target) r = m; //核心
else l = m;
}
cout << r;
return 0;
}69. x 的平方根
原文地址：https://blog.csdn.net/2301_76758064/article/details/142056124
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！