【算法——二分查找】

理论基础：

程序员面试经典题，二分搜索一个区间，区间查找 (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）！