【algorithm】算法基础课---二分查找算法（附笔记 | 建议收藏）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
🚀write in front🚀
📝个人主页认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏AcWing算法学习笔记
💬总结希望你看完之后能对你有所帮助不足请指正共同学习交流 🖊
✉️如果无聊的话就来逛逛我的博客栈吧stack-frame.cn
文章目录
前言
关于我写这篇博客的目的以及原因
其实很早前我就写过博客关于二分法但是我是不满意的或是我觉得不完美的于是寒假我又花费三天时间又学了一次今天就把我所学到的经验和知识输出出来以供复习和学习。
声明这里知识基于算法小抄与深入浅出的程序设计两本书+AcWing算法课侵权删
提示以下是本篇文章正文内容下面案例可供参考
一、二分查找的思想
由于找一个数遍历的时间复杂度有些题目会超时所以就需要一个更加优秀的算法—二分查找算法其实二分算法可以将时间复杂度缩小到logN 想一想为什么
那么废话不多说下面就来讲二分查找的基本思想
我们开始定义两个变量leftright分别指向数组的左端点和右端点这里会出现左闭右开以及都是闭区间的边界问题这个问题下面单独会讲解大家不用着急
利用数学上边的二分法就是一次检查一半这样就可以一次去除一半的不符合要求的数据大大加大了效率通过不断地迭代进而二分出正确答案。
二、二分查找的模板
1.寻找⼀个数基本的⼆分搜索
这个场景是最简单的肯能也是⼤家最熟悉的即搜索⼀个数如果存在
返回其索引否则返回 -1。
这里再把二分模板的代码附上
这里是一个左闭右开区间
//数组 //目标 //数组长度
int binarySearch(int* nums, int target, int size)
{
//特殊情况可以了解一下这里不计入模板
//if(nums==NULL||size==0)
// return -1;
int left=0,right=size-1;
while(left<right)
{
int mid=left+(right-left)/2;//防止溢出
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
if(nums[left]!=target) return -1;
else return left;
}
这里是一个左右都闭的方法
//数组 //目标 //数组长度
int binarySearch(int* nums, int target, int size)
{
//特殊情况可以了解一下这里不计入模板
//if(nums==NULL||size==0)
//return -1;
int left=0,right=size-1;
while(left<=right)
{
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
if(nums[left]!=target) return -1;
else return left;
}
2.边界问题
1、为什么 while 循环的条件中是 <=⽽不是 <
因为初始化 right 的赋值是 size - 1 即最后⼀个元素的索
引⽽不是 size 。
这⼆者可能出现在不同功能的⼆分查找中区别是前者相当于两端都闭区
间 [left, right] 后者相当于左闭右开区间 [left, right) 因为索引⼤
⼩为 size 是越界的。
我们这个算法中使⽤的是前者 [left, right] 两端都闭的区间。这个区间
其实就是每次进⾏搜索的区间。
什么时候应该停⽌查找呢当然找到了⽬标值的时候可以终⽌
if(nums[mid] == target)
return mid;
但如果没找到就需要 while 循环终⽌然后返回 -1。那 while 循环什么时
候应该终⽌查找区间为空的时候应该终⽌意味着你没得找了就等于没
找到嘛。
while(left <= right) 的终⽌条件是 left == right + 1 写成区间的形式
就是 [right + 1, right] 或者带个具体的数字进去 [3, 2] 可⻅这时候
区间为空因为没有数字既⼤于等于 3 ⼜⼩于等于 2 的吧。所以这时候
⼆分查找解题套路框架
while 循环终⽌是正确的直接返回 -1 即可。
while(left < right) 的终⽌条件是 left == right 写成区间的形式就是
[left, right] 或者带个具体的数字进去 [2, 2] 这时候区间⾮空还
有⼀个数 2但此时 while 循环终⽌了。也就是说这区间 [2, 2] 被漏掉
了索引 2 没有被搜索如果这时候直接返回 -1 就是错误的。
当然如果你⾮要⽤ while(left < right) 也可以我们已经知道了出错的
原因就打个补丁好了
//...
while(left < right) {
// ...
}
return nums[left] == target ? left : -1;
2、为什么 left = mid + 1 right = mid - 1 我看有的代码是 right =
mid 或者 left = mid 没有这些加加减减到底怎么回事怎么判断
这也是⼆分查找的⼀个难点不过只要你能理解前⾯的内容就能够很
容易判断。
本算法的查找区间是两端都闭的
即 [left, right] 。那么当我们发现索引 mid 不是要找的 target 时下
⼀步应该去搜索哪⾥呢
当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对因为 mid 已
经搜索过应该从搜索区间中去除。
3、此算法有什么缺陷
我想你应该已经掌握了该算法的所有细节以及这样处理的原因。但
是这个算法存在局限性。
⽐如说给你有序数组 nums = [1,2,2,2,3] target 为 2此算法返回的索
引是 2没错。但是如果我想得到 target 的左侧边界即索引 1或者我
想得到 target 的右侧边界即索引 3这样的话此算法是⽆法处理的。
⼆分查找解题套路框架
这样的需求很常⻅你也许会说找到⼀个 target然后向左或向右线性搜
索不⾏吗可以但是不好因为这样难以保证⼆分查找对数级的复杂度
了。
我们后续的算法就来讨论这两种⼆分查找的算法。
3.寻找左侧边界的⼆分搜索
//数组 //目标 //数组长度
int binarySearch(int* nums, int target, int size)
{
//特殊情况可以了解一下这里不计入模板
//if(nums==NULL||size==0)
// return -1;
int left=0,right=size;//注意
while(left<right)
{
int mid=left+(right-left)/2;//防止溢出
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
if(nums[left]!=target) return -1;
else return left;
}
1、为什么 while 中是 < ⽽不是 <= ?
⽤相同的⽅法分析因为 right = size ⽽不是 size - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。
while(left < right) 终⽌的条件是 left == right 此时搜索区间 [left, left) 为空所以可以正确终⽌。
PS这⾥先要说⼀个搜索左右边界和上⾯这个算法的⼀个区别也是很多
读者问的刚才的 right 不是 size - 1 吗为啥这⾥⾮要写成
size 使得「搜索区间」变成左闭右开呢
因为对于搜索左右侧边界的⼆分查找这种写法⽐较普遍我就拿这种写法
举例了保证你以后遇到这类代码可以理解。你⾮要⽤两端都闭的写法反⽽
更简单我会在后⾯写相关的代码把三种⼆分搜索都⽤⼀种两端都闭的写
法统⼀起来你耐⼼往后看就⾏了。
2、为什么没有返回 -1 的操作如果 nums 中不存在 target 这个值怎
么办
因为要⼀步⼀步来先理解⼀下这个「左侧边界」有什么特殊含义
对于这个数组算法会返回 1。这个 1 的含义可以这样解读 nums 中⼩于
2 的元素有 1 个。
⽐如对于有序数组 nums = [2,3,5,7] , target = 1 算法会返回 0含义
是 nums 中⼩于 1 的元素有 0 个。
再⽐如说 nums = [2,3,5,7], target = 8 算法会返回 4含义是 nums
中⼩于 8 的元素有 4 个。
⼆分查找解题套路框架
综上可以看出函数的返回值即 left 变量的值取值区间是闭区间
[0, size] 所以我们简单添加两⾏代码就能在正确的时候 return
-1;
3、为什么 left = mid + 1 right = mid 和之前的算法不⼀样
这个很好解释因为我们的「搜索区间」是 [left, right) 左闭右
开所以当 nums[mid] 被检测之后下⼀步的搜索区间应该去掉 mid 分
割成两个区间即 [left, mid) 或 [mid + 1, right) 。
4、为什么返回 left ⽽不是 right ?
都是⼀样的因为 while 终⽌的条件是 left == right 。
int left_bound(int[] nums, int target)
{
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
}
else if (nums[mid] > target)
{
// 搜索区间变为 [left, mid-1]
right = mid - 1;
}
else if (nums[mid] == target)
{
// 收缩右侧边界
right = mid - 1;
}
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
4.寻找右侧边界的⼆分查找
int right_bound(int[] nums, int target)
{
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
}
else if (nums[mid] > target)
{
// 搜索区间变为 [left, mid-1]
right = mid - 1;
}
else if (nums[mid] == target)
{
// 收缩右侧边界
left = mid - 1;
}
}
}
// 检查出界情况
if (lright < 0 || nums[right] != target)
return -1;
return right;
}
思路类似左边界。
三、经典题目集
int search(int* nums, int numsSize, int target)
{
int left=0,right=numsSize-1;
while(left<=right)
{
int mid=left+(right-left)/2;
if(nums[mid]==target)
{
return mid;
}
else if(nums[mid]>target)
{
right=mid-1;
}
else if(nums[mid]<target)
{
left=mid+1;
}
}
return -1;
}
// int search(int* nums, int numsSize, int target)
// {
// int left=0,right=numsSize-1;
// while(left<right)
// {
// int mid=(right+left)/2;
// if(nums[mid]>=target) right=mid;
// else left=mid+1;
// }
// if(nums[left]!=target) return -1;
// else return left;
// }
int searchInsert(int* nums, int numsSize, int target)
{
int left=0,right=numsSize-1,ans=numsSize;
while(left<=right)
{
int mid=left+(right-left)/2;
if(nums[mid]>=target)
{
ans=mid;
right=mid-1;
}
else left=mid+1;
}
return ans;
}
// {
// int left=0,right=numsSize;
// while(left<right)
// {
// int mid=(left+right)/2;
// if(nums[mid]>=target) right=mid;
// else left=mid+1;
// }
// return left;
// }
/*
* 输入 **matrix 是长度为 matrixSize 的数组指针的数组其中每个元素也是一个数组
* 的长度组成 *matrixColSize 数组作为另一输入*matrixColSize 数组的长度也为 matrixSize
*/ //二维数组 //数组长度 //一维数组 //目标数字
bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target)
{
if(matrix==NULL || matrixSize==0 || *matrixColSize==0)
return false;
int row=matrixSize; //行数
int col=matrixColSize[0];
int i=0;
int j=col-1;
while(i<row && j>=0)
{
if(matrix[i][j]==target) return true;
else if(matrix[i][j]>target) j--;
else if(matrix[i][j]<target) i++;
}
return false;
}
总结
1、分析⼆分查找代码时不要出现 else全部展开成 else if ⽅便理解。
2、注意「搜索区间」和 while 的终⽌条件如果存在漏掉的元素记得在
最后检查。
3、如需定义左闭右开的「搜索区间」搜索左右边界只要在 nums[mid] == target 时做修改即可搜索右侧时需要减⼀。
4、如果将「搜索区间」全都统⼀成两端都闭好记只要稍改 nums[mid] ==target 条件处的代码和返回的逻辑即可推荐拿⼩本本记下作为⼆分搜索模板。
我是夏目浅石希望和你一起学习进步刷题无数希望各位大佬能一键三连支持一下博主hhhh~我们下期见喽
特别注意本次博客基于算法小抄以及AcWing算法课写出来的内容如果想进一步学习希望您可以自己看书+看视频。
