【刷题日记】为什么二分查找总是写不对?
二分查找的逻辑本身并不复杂,但是在实际写代码的时候我们总是出错,要么少写个等于号,要么漏掉一个元素。出现这些问题的原因在于没有把握好对循环不变量的掌控。当对自己写出的循环没把握时,各种细节问题会频繁出现,从而成为我的二分恐惧症、快排恐惧症以及链表恐惧症的原因之一。
本文通过红蓝染色法,通过对循环不变量的正确理解快速写出正确的二分查找代码。
本文例题
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 的算法解决此问题。
利用数组有序的性质我们可以写出二分查找算法。
在解这道题之前我们先考虑以下子问题:给定一个按照非递减顺序排列的整数数组 nums
和一个目标值 target
,找出给定目标值在数组中的开始位置,即大于等于 target
的第一个数所表示的下标。
三种区间写法
在以下的代码中,l
表示左指针,r
表示右指针,mid
表示中点,指向被询问的数。
在选取中点时我们通常有:int mid = (l+r)/2;
,但是为了避免在一些语言中(C、Java)加法出现溢出的状况,我们还可以这样写:int mid = l+(r-l)/2;
。
原理:
红蓝染色法:对一个数组的数字进行染色,左边染红色,右边染蓝色。对应问题中来讲:染红色的表示 false
,即表示 <target
的数;染蓝色的表示 true
,即表示 >=target
的数。right
左移使右侧变蓝,left
右移使左侧变红。
对于不同的区间表示方式,二分查找会有不同的写法,这也是为什么我们在看 LeetCode 题解时二分查找写法总是有一些细微差别的原因。
闭区间写法
闭区间写法要求循环开始时 l
和 r
指向的「未确定颜色」区间是闭区间。
1 | public int lowerBound(int[] nums,int target){ |
每一次循环后,l-1
前的数必定是红色的,r+1
以后的数必是蓝色的。这就是循环不变量!
最终染色完毕得到以下结果:
if
中的条件判定可以写成判定染蓝色的条件。左闭右开写法
把握好循环不变量,你可以轻松写出另一种写法。
1 | public int lowerBound2(int[] nums,int k){ |
开区间写法
开区间写法中,l
或 r
的变化不需要 +1。
1 | public int lowerBound3(int[] nums,int k){ |
三种写法喜欢那种写那种,只要把握好循环不变量想写那种写那种,都不会混乱。
target
的类型
在前面的二分查找中,我们考虑的子问题是找出大于等于 target
的第一个数所表示的下标。如果我们要求出大于/小于/小于等于 target
的第一个数/最后一个数所表示的下标该怎么做?
当数组中的数都是整数时,其实我们可以将大于/小于/小于等于转化为大于等于:
- 大于
target
的第一个数的下标:大于等于target
+1 的数的下标 - 小于
target
的最后一个数的下标:大于等于target
的数下标 -1 - 小于等于
target
的最后一个数的下标:大于等于target
+1 的数的下标 -1
那回到题目 🟨 34. 在排序数组中查找元素的第一个和最后一个位置,题目要求的就是:
- 找出大于等于
target
的第一个数所表示的下标 - 找出小于
target
+1 的最后一个数所表示的下标
我们就可以根据此写出相应的代码。
数组中不存在符合题意的数
在题目🟨 34. 在排序数组中查找元素的第一个和最后一个位置 中还有个要求就是,如果不存在 target
需要返回 -1
,那么我们检查二分查找(大于等于 target
的第一个数所表示的下标)返回的下标对应的数组是否是 target
即可。如果根本不存在大于等于 target
的第一个数所表示的下标,l
最终会到达 nums.length
,这时候返回 -1
即可。
因此总的代码为:
1 | public int[] searchRange(int[] nums, int target) { |
复杂度分析:
- 时间复杂度:
- 空间复杂度:
区间边界的传入
可以把 l
或 r
作为参数传进二分查找的算法当中。
1 | public int lowerbound(int[] nums,int l,int r,int target){ |
相关题目
二分查找难点:
- 想不到使用二分查找解决
- 存在单调性质的数组(从而导致答案二值性)适合使用二分查找
- 「最小化最大值」和「最大化最小值」是二分查找的关键词
- 编写染色函数困难
练习题:
- 🟩 2529. 正整数和负整数的最大计数 - 力扣(LeetCode) 要求使用时间复杂度为 的解法
- 🟨 2300. 咒语和药水的成功对数 - 力扣(LeetCode)
- 🟨 2563. 统计公平数对的数目 - 力扣(LeetCode) 关键理解点在于排序不影响答案
- 🟨 275. H 指数 II - 力扣(LeetCode) 考察对于红蓝染色的灵活掌握
- 🟨 875. 爱吃香蕉的珂珂 - 力扣(LeetCode) 考察染色函数编写
- 🟨 2187. 完成旅途的最少时间 - 力扣(LeetCode) 和上题差不多
- 🟨 2861. 最大合金数 - 力扣(LeetCode) 要点在于阅读理解题目含义
- 🟨 2439. 最小化数组中的最大值 - 力扣(LeetCode) 「最小化最大值」就是二分答案的代名词。
- 🟨 2517. 礼盒的最大甜蜜度 - 力扣(LeetCode)
进阶练习,在 0 到 n-2 中进行二分:
- 🟨 162. 寻找峰值 - 力扣(LeetCode) 注意到,可以利用「最右侧元素」一定是蓝色的特点优化二分
- 🟨 153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)
- 🟨 33. 搜索旋转排序数组 - 力扣(LeetCode)
- 🟨 81. 搜索旋转排序数组 II - 力扣(LeetCode)