二分查找的逻辑本身并不复杂,但是在实际写代码的时候我们总是出错,要么少写个等于号,要么漏掉一个元素。出现这些问题的原因在于没有把握好对循环不变量的掌控。当对自己写出的循环没把握时,各种细节问题会频繁出现,从而成为我的二分恐惧症、快排恐惧症以及链表恐惧症的原因之一。

本文通过红蓝染色法,通过对循环不变量的正确理解快速写出正确的二分查找代码。

本文例题

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(logn)O(\log n) 的算法解决此问题。

利用数组有序的性质我们可以写出二分查找算法。

在解这道题之前我们先考虑以下子问题:给定一个按照非递减顺序排列的整数数组 nums 和一个目标值 target,找出给定目标值在数组中的开始位置,即大于等于 target 的第一个数所表示的下标。

三种区间写法

在以下的代码中,l 表示左指针,r 表示右指针,mid 表示中点,指向被询问的数。

中点选取的写法以防溢出

在选取中点时我们通常有:int mid = (l+r)/2;,但是为了避免在一些语言中(C、Java)加法出现溢出的状况,我们还可以这样写:int mid = l+(r-l)/2;

原理:l+r2=rl+2l2=rl2+l=l+rl2\lfloor \frac{l+r}{2} \rfloor = \lfloor \frac{r-l+2l}{2} \rfloor = \lfloor \frac{r-l}{2} +l \rfloor = l+ \lfloor \frac{r-l}{2} \rfloor

红蓝染色法:对一个数组的数字进行染色,左边染红色,右边染蓝色。对应问题中来讲:染红色的表示 false,即表示 <target 的数;染蓝色的表示 true,即表示 >=target 的数。right 左移使右侧变蓝,left 右移使左侧变红。

对于不同的区间表示方式,二分查找会有不同的写法,这也是为什么我们在看 LeetCode 题解时二分查找写法总是有一些细微差别的原因。

闭区间写法

闭区间写法要求循环开始时 lr 指向的「未确定颜色」区间是闭区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int lowerBound(int[] nums,int target){
int l=0,r = nums.length-1;
int mid;
while(l<=r){ // 【要点】while中要求l,r表示的区间不为空
mid = l+ (r-l)/2; // 避免溢出问题
// 染色
if(nums[mid]<target) // 这里写的条件是判定染红色的条件
// 染红色
l=mid+1; // l-1 全都小于 k
else
r=mid-1;
}
return l; // 或 r+1
}

每一次循环后,l-1 前的数必定是红色的,r+1 以后的数必是蓝色的。这就是循环不变量

最终染色完毕得到以下结果:

image.png

试一试:将 if 中的条件判定可以写成判定染蓝色的条件。

左闭右开写法

把握好循环不变量,你可以轻松写出另一种写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int lowerBound2(int[] nums,int k){
int l=0,r = nums.length; // 变动点:r指向开区间边界
int mid;
while(l<r){ // 变动点:把握区间不为空
mid = l+ (r-l)/2;
if(nums[mid]<k){
l=mid+1;
}else{
r=mid; // 变动点
}
}
return l; // 或 r
}

开区间写法

开区间写法中,lr 的变化不需要 +1。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int lowerBound3(int[] nums,int k){
int l=-1,r = nums.length; // 变动点
int mid;
while(l+1!=r){ // 变动点
mid = l+ (r-l)/2;
if(nums[mid]<k){
l=mid;
}else{
r=mid; // 变动点
}
}
return l+1; // 或 r // 变动点
}

三种写法喜欢那种写那种,只要把握好循环不变量想写那种写那种,都不会混乱。

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] searchRange(int[] nums, int target) {
if(nums.length==0)return new int[]{-1,-1};
int a = lowerBound(nums,target);
int b = lowerBound(nums,target+1)-1;
a = a<nums.length&&nums[a]==target? a:-1;
b = b>=0&&nums[b]==target? b:-1;
return new int[]{a,b};
}

public int lowerBound(int[] nums,int k){
int l=-1,r = nums.length;
int mid;
while(l+1!=r){
mid = l+ (r-l)/2;
if(nums[mid]<k){
l=mid;
}else{
r=mid;
}
}
return r;
}

复杂度分析:

  • 时间复杂度:O(logn)O(\log n)
  • 空间复杂度:O(1)O(1)

区间边界的传入

可以把 lr 作为参数传进二分查找的算法当中。

1
2
3
4
5
6
7
8
9
10
11
12
public int lowerbound(int[] nums,int l,int r,int target){
int mid;
while(l<=r){
mid = l+(r-l)/2;
if(nums[mid]<target){
l=mid+1;
}else{
r=mid-1;
}
}
return l;
}

相关题目

二分查找难点:

  • 想不到使用二分查找解决
    • 存在单调性质的数组(从而导致答案二值性)适合使用二分查找
    • 「最小化最大值」和「最大化最小值」是二分查找的关键词
  • 编写染色函数困难

练习题:

进阶练习,在 0 到 n-2 中进行二分:

本文参考