本文是学习「每日一题」组织AlgoWiki的二分查找的学习笔记,本篇二分查找是由weiwei大佬贡献,原文地址:「https://ojeveryday.github.io/AlgoWiki/#/BinarySearch/README」。「每日一题」组织是一起刷题的大家庭,群里有LeetCode网站精品题解的作者weiwei大佬、甜姨和群主。如果有兴趣加入「每日一题」组织,请访问网址:「https://group.ojeveryday.com/#/check」。
在weiwei大佬的二分查找中,有三个版本的「二分查找」的模板。
ps:在第二个版本学习过程中,需要考虑的细节较少,可以处理一些比较复杂的问题。但是在初学过程中,可能会陷入死循环,可以通过debug的方式查找死循环的位置,并进一步理解。
在学习模板一过程中,结合「力扣」题目二分查找进行学习。
在一个有序的数组中查找某一个元素,就好比「猜价格」游戏,当价格猜高之后,我们适当降低价格,当价格猜低之后,则适当抬高价格。
将待搜索的区间,左边界设置为left
,右区间设置为right
。将带搜索的区间[left, right]
可以分为以下三部分:
mid
位置,仅包含一个元素;[left, mid-1]
之间的所有元素;[mid+1, right]
之间的所有元素。于是二分查找就是根据mid=(left+right)/2
位置的元素nums[mid]
的值与target
的关系,来不断改变left
或者right
的值。
nums[mid] == target
,则返回mid
;nums[mid] < target
,因为数组有序,则mid
位置左侧的所有元素的值均小于target
,则令left = mid + 1
;nums[mid] > target
,,因为数组有序,则mid
位置右侧的所有元素的值均大于target
,则令right = mid - 1
。class Solution {
public int search(int[] nums, int target) {
// 用于特值判断
int length = nums.length;
if (length <= 0) {
return -1;
}
int left = 0;
int right = length - 1;
while (left <= right) {
// 为了防止left + right 整形溢出,写成如下形式:left + (right - left) / 2 《=》 (left + right) / 2
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// 下一轮搜索区间:[mid + 1, right]
left = mid + 1;
} else {
// 下一轮搜索区间:[left, mid - 1]
right = mid - 1;
}
}
return -1;
}
}
考虑不仔细是学习「二分查找」容易出错的地方,这里切记不要跳过某些步骤,需要想清楚每一行代码、每一个步骤的作用:
left
或者right
的值,将每次搜索的区间不断变小,达到「缩减问题规模」的目的。while
循环中使用的条件为(left <= right)
,当left == right
时,所需要查找的区间中仅存在一个元素,此时也必须去查找下去。(left + right)
的值存在整型范围溢出的可能,所以将mid = (left + right) / 2
变化为mid = left + (right - left) / 2
,由数学推导可知两式等价。这个模板二也是weiwei大佬的力推版本,这个版本在编写时需要考虑的细节比较少,不容易出现错误。
public int search(int[] nums, int left, int right, int target) {
while (left < right) {
// 选择中位数时,向下取整
int mid = left + (right - left) / 2;
if (check(mid)) {
// 下一轮搜索区间:[mid + 1, right]
left = mid + 1;
} else {
// 下一轮搜索区间:[left, mid]
right = mid;
}
}
// 当退出循环时,仅有一个位置没有看到。即left = right的位置
// 视情况,是否需要单独判断 left (或者 right)这个下标的元素是否符合题意
return -1;
}
public int search(int[] nums, int left, int right, int target) {
while (left < right) {
// 选择中位数时,向上取整
int mid = left + (right - left + 1) / 2;
if (check(mid)) {
// 下一轮搜索区间:[left, mid - 1]
right = mid - 1;
} else {
// 下一轮搜索区间:[mid, right]
left = mid;
}
}
// 当退出循环时,仅有一个位置没有看到。即left = right的位置
// 视情况,是否需要单独判断 left (或者 right)这个下标的元素是否符合题意
return -1;
}
理解代码模板的要点:
while (left < right)
来看,当区间中仅有两个元素时,依然可以进行循环操作。也就是说,当退出循环时,一定有left == right
,这一点在确定元素下标位置时,极其有用。nums[mid]
何时不是目标元素,进而改变left
和right
的值,缩小搜索区间。注意事项:
left
和right
的值进行特殊判断,这一步叫「后处理」。在一些问题中,排除了其他不符合要求的元素后,剩下的那1个元素就一定是目标元素。left = mid
后,它对应取中位数的方法一定是int mid = left + (right - left + 1) / 2
在本题中查找一个目标值,并返回其下标;如果不存在目标值,则返回插入位置的下标值。这也是典型的二分查找类型题目,使用模板2来解决问题。每次排除不符合的区间,逐步缩小区间范围。参考代码如下所示。在代码中需要理解为何在nums[mid] < target
时,直接将left = mid + 1
,因为在题目中需要找到target
的位置或者插入位置,小于目标值的元素所在的位置一定不是我们要找的下标。
class Solution {
public int searchInsert(int[] nums, int target) {
int length = nums.length;
if (nums.length <= 0) {
return 0;
}
// 特殊边界判断
if (nums[length - 1] < target) {
return length;
}
int left = 0;
int right = length - 1;
while (left < right) {
// 使用右移代替除法
int mid = (left + right) >>> 1;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
// 退出循环后,一定有left == right
return left;
}
}
复杂度分析:
在weiwei大佬的二分查找文档中,还列举了第三种模板。模板三与模板二很相似,但是需要考虑更多的细节。
public int search(int[] nums, int left, int right, int target) {
while (left + 1 < right) {
// 选择中位数时下取整
int mid = left + (right - left) / 2;
if (nums[mid] == target){
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if (nums[left] == target) {
return left;
}
if (nums[right] == target) {
return right;
}
return -1;
}
通过观察模板三可以发现与模板二之间的差别:
while (left + 1 < right)
,在退出循环时一定有left + 1 == right
,也就是在退出循环后,区间中含有[left,right]
两个元素。left + 1 < right
的写法,语义性不如left < right
和left <= right
。在确认一个有范围的整数时,自然数本身就是有序的,自然可以使用二分查找进行问题的处理。
注意:这种类型的题目,一般判断条件都不是简单的表达式,需要抽象出来为一个单独的函数进行处理。
需要注意「二分查找」不是只能应用到「有序数组中」,只要是「减治思想」都可以进行应用。
题目 | tips | 参考代码 |
---|---|---|
34. 在排序数组中查找元素的第一个和最后一个位置 | 非常是和实用模板2来进行求解 | 力扣「在排序数组中查找元素的第一个和最后一个位置」 |
153. 寻找旋转排序数组中的最小值 | 必做题 | 力扣「寻找旋转排序数组中的最小值」 |
33. 搜索旋转排序数组 | 必做题 | 力扣「二分查找-33. 搜索旋转排序数组」 |
「1095. 山脉数组中查找目标值」 | 三次二分查找寻找山脉数组目标值 | 力扣「二分查找-「力扣」1095. 山脉数组中查找目标值」 |
未完待续~~