Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky.

-Donald Knuth

引例

给定数组[1, 2, 3, 5, 5, 5, 8, 9].
1.找到第一个">=5"的元素
2.找到最后一个"<5"的元素
3.找到第一个">5"的元素
4.找到最后一个"<=5"的元素

二分法有两个易错点，一是开区间闭区间理不清楚死循环，二是理不清关系>= >傻傻转不明白。

开区间闭区间问题

一般的，我们可以认为二分法代码有以下几步。

声明初始变量。
进入非空循环区间
根据条件移动左右指针

左闭右闭[left, right]

我个人的思维方式。

1
2
3
4
5
6
7


int left = 0;
int right = length - 1;//初始位置，因为闭区间，所以选择末端两个元素即可
while(left <= right) {//保证区间不为空即可。left == right 依旧非空
    其他代码块;
    left = middle + 1;
    right = middle - 1; //由于已经包括端点，所以直接跳到端点下一个位置
}

左闭右开[left, right)

符合美国人思维的写法。

1
2
3
4
5
6
7


int left = 0;
int right = length;//初始位置，由于右端点开区间所以直接选择数组长度即可
while(left < right) {//[a,a+1)区间不为空
    其他代码块;
    left = middle + 1;
    right = middle; //每次比较并没有包括右端点，所以直接赋值右端点即可
}

左开右开(left, right)

可能有人习惯这么写。

1
2
3
4
5
6
7


int left = -1;
int right = length;//初始位置，由于右端点开区间所以直接选择数组长度即可
while(left + 1 < right) {//(a,a+2)区间不为空
    其他代码块;
    left = middle;
    right = middle; //每次比较并没有包括左右端点，所以直接赋值左右端点即可
}

带等号和不带等号，if里面到底怎么写

先说结论，关注循环不变量：L-1始终满足if里面的条件，R+1始终满足else里面的条件。

关键不在于区间里的元素具有什么性质，而是区间外面的元素具有什么性质。

我们可以将left定义为第一个大于等于target的值。那么从始至终，left都是满足这个定义的，right同理。

循环不变量在边界处理、循环处理中非常常见，在写代码中会越发感叹其精妙之处。

此处的区间外面，亦可以是开区间端点。「灵感就像鼻尖稍纵即逝的香味，而时间就像风。2024/1/21留」

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


//闭区间写法
int left = 0;
int right = nums.length - 1;
while(left <= right) {
	mid = right + (left - right) / 2;
    if(nums[mid] < target){
        left = mid + 1; //那么所有的left - 1 都满足 nums[left - 1] < target,left -1即所谓的区间外面
    }
    else {
        right = mid - 1; //那么所有的right + 1 都满足 nums[right - 1] >= target,right + 1即所谓的区间外面
    }
}

最后回到开头的问题，最后一个<5的问题可以转化为第一个大于等于5的位置前一个位置，第一个>5的问题转化为第一个>=6的位置，最后一个<=5的问题转化为第一个>=6的前面一个位置的问题。因此所有问题都转化为>=的问题。套用模板即可完成问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


//闭区间写法
int left = 0;
int right = nums.length - 1;
//闭区间写法
while(left <= right) {
	mid = right + (left - right) / 2;
    if(nums[mid] < target){
        left = mid + 1;//那么所有的left - 1 都满足 nums[left - 1] < target,left -1即所谓的区间外面
    }
    else {
        right = mid - 1;//那么所有的right + 1 都满足 nums[left - 1] >= target,right + 1即所谓的区间外面
    }
}
return right + 1;//第一个>=target的数字的位置

注意：如果是找到第一个数字和最后一个数字的问题，在转化为target+1的位置时还需要判断前一个位置是否满足要求。

LeetCode#34

题目描述：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

题解：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int left = 0;
        int right = nums.length - 1;
        if(nums.length == 0) {
            return result;
        }
        //找到第一个大于等于target的位置
        while(left <= right) {
            int middle = left + (right - left) / 2;
            if(nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        if(right + 1 != nums.length &&nums[right + 1] == target) {//判断是否满足==target的要求
            result[0] = right + 1;
        }
        left = 0;
        right = nums.length - 1;
        //找到第一个大于等于target + 1的位置
        while(left <= right) {
            int middle = left + (right - left) / 2;
            if(nums[middle] < target + 1) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        if(right != -1 && nums[right] == target) {////判断是否满足==target的要求
            result[1] = right;
        }
        return result; 
    }
}

算法拾遗-二分查找

引例