CC53.【C++ Cont】二分查找的普通模版

目录

1.知识回顾

2.关键点

特点

三个模版

普通的模版(有局限)

以LeetCode上的一道题为例:704. 二分查找

分析

引入二段性:分两段,舍一段,操作另一段(这个是二分查找的本质!)

代码

提交结果

当然也可以使用随机数来分两段

普通模版总结

---

1.知识回顾

之前在C语言专栏中的文章提到了二分查找,可复习:

E7.【C语言】练习：在一个有序数组中查找具体的某个数字n（二分查找）

本文将提炼出一些关键点

2.关键点

特点

算法细节较多,一 一介绍:

之前讲过二分查找的前提: 数组有序时才能使用二分查找,其实并不是这样!,

当数组满足某特定规律时,也可以使用二分查找(这个后面会介绍)

三个模版

有以下二分查找的固定格式,做题只需要照葫芦画瓢,注意先理解再记忆

普通的模版(有局限)

以LeetCode上的一道题为例:704. 二分查找

https://leetcode.cn/problems/binary-search/description/

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

分析

暴力解法直接从左向右或从右向左找,这里不写,讲讲暴力解法的缺陷:每次只能比较一个数,时间复杂度为

注意到题目条件"一个 n 个元素有序的（升序）整型数组 nums ",那么可以利用数组的单调性对暴力解法优化

以nums = [-1,0,3,5,9,12], target = 9为例说明,现查找到3,发现target>3且数组单增,那么3的左侧是不需要查找的,继续查找3的右侧

引入二段性:分两段,舍一段,操作另一段(这个是二分查找的本质!)

对于上述单增数组有许多分段方式:

1.二分

即近似分成二等分

2.三分

将数组近似分成三等分

然后任意选一个节点来分段,例如:

3.四分

将数组近似分成四等分......

......

当然也可以使用随机数来分段

其中二分的时间复杂度是最低的,时间复杂度为,当然某些情况下使用随机数来分段时间复杂度也比较低

算法:设数组是单调递增的,对它平分两段:

比较nums[mid]和num[target]的大小,

1.nums[mid]==num[target],结束循环,返回结果

2.nums[mid]num[target],依据二段性:分两段,舍一段,操作另一段

,舍弃[left,mid]段,去[mid,right]段寻找,那么更新left

left=mid+1;//right不变

nums[mid]num[target],返回结果,依据二段性:分两段,舍一段,操作另一段

,舍弃[mid,right]段,去[left,mid]段,那么更新right

right=mid-1;//left不变

3.更新mid(有多种方法,上面提过了)

只需要循环上面三步,变化寻找的区间,最终一定可以找到结果

结束循环的两个条件:

1.nums[mid]==num[target],直接返回结果

2.leftright,(注:left==right,分的段是一个"点",只有一个元素,但也需要判断是否等于target,仍然需要循环),没有找到target

那么循环的条件是:leftright

代码

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

注:mid不要写成(left+right)/2!之前在L42.【LeetCode题解】四数之和(双指针思想) 从汇编角度分析报错原因文章提到过报错的原因,当数组过长时,加法可能导致溢出

防溢出的方法:(left+right)/2改为left+(right-left)/2或left+(right-left+1)/2

提交结果

同理三分法只需要将除数2改成3即可,四分法、五分法同理

mid=left+(right-left+1)/3;

当然也可以使用随机数来分两段

class Solution {
public:int search(vector<int>& nums, int target) {srand((unsigned int)time(nullptr));int left=0;int right=nums.size()-1;int mid;while(left<=right){mid=left+rand()%(right - left + 1);if (nums[mid]==target)return mid;if (nums[mid]>target)right=mid-1;if (nums[mid]<target)left=mid+1;   }return -1;}
};

注: 循环体中,如果最后更新mid将导致除0错误!

这样写是错误的:

class Solution {
public:int search(vector<int>& nums, int target) {srand((unsigned int)time(nullptr));int left=0;int right=nums.size()-1;int mid=left+rand()%(right - left + 1);while(left<=right){if (nums[mid]==target)return mid;if (nums[mid]>target)right=mid-1;if (nums[mid]<target)left=mid+1;mid=left+rand()%(right - left + 1);   }return -1;}
};

排查错误:

VS中进入调试模式

发生错误的地方是: mid = left + rand() % (right - left + 1),则mid=2+rand()%(1-2+1)=2+rand()%0,为除0错误,此时left仍然<=right,策略:先更新mid的值,这样进行if判断时能修改left和right的值,能及时退出循环,防止除0错误

提交结果:

普通模版总结

利用二段性填以下模版空缺的地方:

while(left<=right)
{int mid=left+(right-left+1)/2;if (......)return mid;if (......)right=mid-1;if (......)left=mid+1;  
}

注意1.判断条件 2.mid防溢出方法 3.left和right的更新方式

其他两个模版见下一篇文章