写在前面: (一)二分法的思想十分容易理解,但是二分法边界处理问题大多数人都是记忆模板,忘记模板后处理边界就一团乱(👁:“我懂了”, ✋ :”你懂个🔨”)因为我此前也是记忆模板,所以现在想通过一边学习,一边将所学记录成博客教出去(费曼学习法),希望以后能自己推导出边界如何处理,而不仅仅是记忆模板。欢迎一起交流学习,如有看法不一样之处也欢迎留言一起讨论! (二)我主要解释了二分法的左闭右闭区间,左闭右开区间两种写法,并且每个写法都举了相应的反例,范围写错的话可能会出现的错误等…
故事分享🏬:
有一天小明到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把小明拦下,要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下,以找出引发警报的书,但是保安露出不屑的眼神:你连二分查找都不会吗?于是保安把书分成两堆,让第一堆过一下报警器,报警器响;于是再把这堆书分成两堆…… 最终,检测了 logN 次之后,保安成功的找到了那本引起警报的书,露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此,图书馆丢了 N – 1 本书。
保安怎么知道只有一本书📖没有登记出借,万一全部都没有登记呢?
这个故事其实说出了二分查找需要的条件
比如在一个有序的数组并且无重复元素的数组中,例如[1, 2, 3, 4, 5, 6],需要查找3的位置就可以使用二分查找。
在二分查找中,目标元素的查找区间的定义十分重要,不同的区间的定义写法不一样
因为查找的区间是不断迭代的,所以确定查找的范围十分重要,主要就是左右区间的开和闭的问题,开闭不一样,对应的迭代方式也不一样,有以下两种方式:
[left, right]
[left, right)
这是一个使用二分查找的例题
题目如下:
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例一:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
示例二:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
提示:
出自704. 二分查找 – 力扣(LeetCode) (leetcode-cn.com)
二分法的思想很简单,因为整个数组是有序的,数组默认是递增的。
二分法就是按照这种方式进行快速排除查找的
tips: 不用去纠结数组的长度是奇数或者偶数的时候,怎么取长度的一半,以下说明,可以跳过。
当数组的长度为奇数的时候:
是奇数的情况很简单,指向中间的数字很容易理解,如果需要查找的数字为29
因为29大于中间的数字大于11,所以左边的所有数字全部排除
当数组的长度为偶数的时候:
这个时候中间的数字两边的数字数量就不一样了(刚开始学习二分法的时候我经常纠结这个问题,和另外一个长度除2得到的是最中间的数吗的问题,我相信不止我一个人纠结过……但其实这是同一个问题,每次长度除2,如果长度为奇数,得到的中间的数字两边数字数量相同,如果长度为偶数就为上图中间的数字两边的相差为 1)
但是千万不要一直纠结中间的数字两边的数字数量不一样这个问题,因为:
所以数组长度是偶数还是奇数这个真的不重要,不影响怎么排除的问题,无非是多排除一个数字或者少排除一个数字
二分法最重要的两个点:
第一种写法:每次查找的区间在[left, right]
(左闭右闭区间),根据查找区间的定义(左闭右闭区间),就决定了后续的代码应该怎么写才能对。因为定义 target 在[left, right]
区间,所以有如下两点:
while(left <= right)
,因为当(left == right)
这种情况发生的时候,得到的结果是有意义的if(nums[middle] > target)
, right 要赋值为 middle – 1, 因为当前的 nums[middle] 一定不是 target ,需要把这个 middle 位置上面的数字丢弃,那么接下来需要查找范围就是[left, middle - 1]
代码如下:
int search(int nums[], int size, int target) //nums是数组,size是数组的大小,target是需要查找的值
{
int left = 0;
int right = size - 1; // 定义了target在左闭右闭的区间内,[left, right]
while (left <= right) {
//当left == right时,区间[left, right]仍然有效
int middle = left + ((right - left) / 2);//等同于 (left + right) / 2,防止溢出
if (nums[middle] > target) {
right = middle - 1; //target在左区间,所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; //target在右区间,所以[middle + 1, right]
} else {
//既不在左边,也不在右边,那就是找到答案了
return middle;
}
}
//没有找到目标值
return -1;
}
下面图解算法的实现过程,建议将代码复制到一个文本编辑器中,边看代码边看图。或者我直接准备了图片,保存下来打开看就好了。
首先看一个数组,需要对这个数组进行操作。需要对33进行查找的操作,那么target 的值就是33
left = 0, right = size - 1
middle = (left + (right - left) / 2 )
if (nums[middle] > target)
,代表middle向右所有的数字大于target
if (nums[middle] < target)
,代表middle向左所有的数字小于target
nums[middle] = 13 < target = 33,left = middle + 1
while (left <= right)
left = 6 <= right = 11
,则继续进行循环
middle = left + ((right - left) / 2)
,计算出 middle 的值
对应第一种正向的写法,我们把循环条件修改看看会发生什么事
修改后题目对应的条件:
代码:
int search(int nums[], int size, int target)
{
int left = 0;
int right = size - 1;
while (left < right) {
//left <= right 修改为 left < right,其他不变
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
//没有找到目标值
return -1;
}
代码图片,边看模拟过程边看代码哦!
好了,现在开始用图片模拟过程
第二种写法:每次查找的区间在 [left, right),(左闭右开区间), 根据区间的定义,条件控制应该如下:
代码如下:
int search(int nums[], int size, int target)
{
int left = 0;
int right = size; //定义target在左闭右开的区间里,即[left, right)
while (left < right) {
//因为left = right的时候,在[left, right)区间上无意义
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle; //target 在左区间,在[left, middle)中
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
// 没找到就返回-1
return -1;
}
代码图片:保存下来边看代码边看图片演示过程
第一步是初始化 left 和 right 的值,然后计算 middle 的值
因为是左闭右开区间,所以数组定义如下:
对应第二种正确的写法,照样把循环条件修改,看会发生什么事
正确的写法中条件为:
修改后题目对应的条件:
代码:
int search(int nums[], int size, int target)
{
int left = 0;
int right = size;
while (left <= right) {
//条件left < right 修改为 left <= right
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
// 没找到就返回-1
return -1;
}
代码图片:(记得边看边保存图片代码边看图片演示哦!)
以下是演示全过程:
二分法最重要的两个点,就是循环条件和后续的区间赋值问题
因为两者是相互联系,相互影响的,所以就需要两者统一,如果两者不统一,就会出现问题
所以循环条件和赋值问题必须统一,也就是循环不变量。
相关题目推荐:
本文相关信息:
❤️完结撒花❤️
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/179265.html原文链接:https://javaforall.cn