【C++算法】二分查找 -＞入门-拓冰企业网站定制

二分，我********

二分查找的介绍

二分查找的特点

在二分查找中，它是最恶心，细节最多，最容易写出死循环的算法，但是只要我们把它弄清楚，去理解，最恶心就会变得最简单了

学习中的侧重点

1、算法原理

使用二分查找，不止可以在数组有序得情况去使用，在我们理解的深刻，那么我们也可以发现一些规律，即使在数组无序中，我们也可以去使用二分优化

2、模板

我们学习二分，一定要去理解模板，不要去死记硬背，理解之后再去记忆，才能发挥最大的功能！

二分查找模板一共有3个：

朴素的二分模板虽然比较简单，但是它有一定的局限性，左边界和右边界其实也算我们的万能模板

开始学习！

一、二、三，上链接！

704. 二分查找 - 力扣（LeetCode）

（一）朴素的二分模板

二分查找算法原理：

1.二分查找算法的本质是利用数组的有序性和二段性进行高效搜索。
2.二段性：通过比较中间元素，将数组分成两个子数组，根据比较结果舍去一部分，继续在另一部分搜索。
3.适用范围：不仅限于有序数组，只要满足二段性即可。

二段性，就是分半，mid = left + (right - left)/2;

例如：在一堆数组，我们要找target

1、如果这个数组，比5小的，也就是1~4，不是我们的目标值，我们是不是可以舍去？答案是的

目标值在5~7的区间里

2、继续搜，是不是如果比5大的，我们也不要呢？答案是的

3、在搜索，如果mid == target，此时这个就是我们的答案，可以直接返回了

最后，为什么可以不要这些值？因为他不是我们需要的值呀，人家要找5，你搜6和7的区间有个屁用？

二分查找算法细节问题：

1.定义left和right指针，初始化搜索区间。
2.循环条件：left <= right。
3.在循环中，计算中间元素的索引mid，并与目标值进行比较。
4.根据比较结果更新left或right指针，缩小搜索区间。
5.如果找到目标元素，返回其索引；如果未找到，返回-1。

class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while(left <= right) { int mid = left + (right - left) / 2;//防止溢出 if(nums[mid] < target) left = mid + 1; else if(nums[mid] > target) right = mid - 1; else return mid; } return -1; } };

mid，为什么这样子写？

int left = 2,000,000,000; // 20亿 int right = 2,000,000,000; // 20亿 int mid = (left + right) / 2; // left + right = 40亿 ❌ 超过 int 最大值 21.47亿！

left = 1,500,000,000 right = 2,000,000,000 right - left = 500,000,000 // ✅ 差值很小，不会溢出 mid = 1,500,000,000 + 250,000,000 = 1,750,000,000 // ✅ 正确

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

（二）查找左边界的二分模板

我们找7，第一个出现的7

为什么r要等于mid？

这仅适用于arr[mid] > target的情况（mid 值已大于 target，mid 及其右边都不可能等于 target）。但如果arr[mid] == target，mid 可能是答案，不能r=mid-1，而应r=mid保留 mid。

为什么l要等于mid+1？

如果arr[mid] < target，整个[l, mid]区间都小于 target，不可能有答案，所以应l = mid+1（排除）。如果arr[mid] >= target，答案可能在[l, mid]，此时不是l=mid，而是r=mid（向左收缩）。

（三）查找右边界的二分模板

同理：

l=mid

arr[mid] <= target：mid 及其左边都可能 ≤ target，但我们想要最右边的，所以答案可能在[mid, r]区间（因为 mid 可能就是答案，也可能右边还有）。此时应保留 mid，收缩左边界：l = mid。

r=mid

arr[mid] > target：mid 的值已经大于 target，那么 mid 及其右边都肯定不是答案，直接排除：r = mid - 1

细节讨论：

循环条件：

left < right √

当left == right的时候，就是最终结果
如果判断容易造成死循环

中点位置：

①left + (right - left) / 2→左中位数（偏左）

②left + (right - left + 1) / 2→右中位数（偏右）

看一个极端例子：left=0, right=1。
如果找最后一个，逻辑是if (arr[mid] <= target) l = mid;
用公式①（偏左，mid=0）→l = 0，区间[0,1]没变，死循环。
用公式②（偏右，mid=1）→l = 1，区间变为[1,1]，正常退出。
如果找第一个，逻辑是if (arr[mid] >= target) r = mid;
用公式②（偏右，mid=1）→r = 1，区间[0,1]没变，死循环。
用公式①（偏左，mid=0）→r = 0，区间变为[0,0]，正常退出。

题目ac代码：

class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { if(nums.size()==0)return {-1,-1}; int begin=0; // 1、找左端点 int l=0,r=nums.size()-1; while(l<r) { int mid=l+(r-l)/2; if(nums[mid]<target) { l=mid+1; }else { r=mid; } } if(nums[l] != target) return {-1,-1}; else begin=l; // 2、找右端点 l=0,r=nums.size()-1; while(l<r) { int mid=l+(r-l+1)/2; if(nums[mid]<=target) { l=mid; }else{ r=mid-1; } } return {begin,r}; } };

总结模板：

资讯详情

【C++算法】二分查找 -＞ 入门