一篇弄懂二分算法

二分查找，时间复杂度为O(log2N)，但是是在有序的前提下，相比O(N)会快特别多，二分的实际应用非常广泛，但是二分有很多种情况，今天就遇到了，特地来总结一下，也是参考一下labuladong的算法秘籍

二分

二分查找（Binary Search) 也叫折半查找。前提要求是数组有序，另外是需要用顺序存储结构。

二分查找可以实现，每次查找都实现数量减半。很简单的一个场景游戏就是猜数字，每一个我们都可以排除掉一半的数字。

模板

二分虽然听起来很简单，但是二分的情况是有很多种的，并且二分的模板不是什么时候都生效的，下面先来看第一道题，LeetCode704 二分查找。

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

大家一看到，模板题，直接上，冲冲冲…

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; 

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1; 
            else if (nums[mid] > target)
                right = mid - 1; 
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这样背模板确实没有啥问题，但是似乎在一些需要进行灵活应用的场景就会有问题了，不理解二分查找的具体原理，我们再来看下面这个题，LeetCode 34 在排序数组中查找元素的第一个和最后一个位置，

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

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

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

是不是背不了模板了，好像这道题不是我们想象的那样，

题型

查找一个数

其实总的来说，我们都可以通过搜索区间来解决这些问题，上述模板题是属于左右都是闭区间的写法，start<=end表示的是我们搜索的区间为[start, end]，这个怎么理解呢，从数学的思维上来理解，我们就可以认为nums就相当于f(x), 而对应的x就是对应的下标，[start, end]代表当查询到[end+1,end]时，才推出循环，而如果上面的模板题就相当于在下图的[start,end]内查找一个等于target的值。

那这一段代码需要怎么理解呢？

else if (nums[mid] < target)
    left = mid + 1; 
else if (nums[mid] > target)
    right = mid - 1; 
1
2
3
4

由于我们采用的[start,end]闭区间的搜索方式，那么我们已经知道mid的值不等于target，那下一步是不是就可以根据这个来确定下一步的搜索区间[start, mid-1], 而如果mid的值小于target，是不是就应该以[mid+1, end]为下一步的搜索区间。

查找最左边界和最右侧边界的搜索

类似的题目我们可以看上面提到的LeetCode 34, 在排序数组中查找元素的第一个和最后一个位置, 其实这个时候我们还是可以通过搜索区间来解决这个问题的，我们先给代码。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);
        return new int[] {left, right};
    }

    public int searchLeft(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length; 
        // [)
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                right = mid;
            else if (nums[mid] < target)
                left = mid + 1; 
            else if (nums[mid] > target)
                right = mid; 
        }
        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }
    // []
    public int searchRight(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; 
        // []
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                left = mid + 1;
            else if (nums[mid] < target)
                left = mid + 1; 
            else if (nums[mid] > target)
                right = mid - 1; 
        }
        if (right < 0 || nums[right] != target) {
            return -1;
        }
        return right;
    }

}
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
38
39
40
41
42
43
44
45
46
47
48
49
50

左边界

我用了两种方法来搜索左边界和右边界，相信通过上面第一道模板题，大家可以理解到，<=和<是为什么？这道题我们就需要明细分析是采用什么搜索区间来进行查找，我们先来看查找左侧边界的值，很明显我们采用的是一个左闭右开的写法[start,end)，由于是右开区间的搜索，我们需要收缩右边界，打一个补丁。

右边界

我们采用的是[start, end], 所于退出条件是left <= right，但是我们需要使用左侧收缩来搜索得到右侧边界，具体和第一道题比较像。

小结

在做二分的时候，我们需要做以下步骤：

1. 确定问题的类型，是找一个数还是找边界。

2. 确定是搜索区间，是采用左闭右开，还是两边都闭。

3. 确定边界收缩方向，即搜索左边界或者右边界。

4. 判断是否需要打补丁（可以从循环退出的条件来进行判断）