二分查找介绍及其变种题目

二分查找法是一个经典查找算法，也是面试中经常出现的一种算法，它以时间复杂度低而著称并广受喜爱。本文整理一些二分的知识并分享一些算法和体验。

时间复杂度

二分查找是一种非常高效的查找算法。假设数据个数是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。

被查找区间的大小变化：

n, n/2, 2/4, n/8, … n/2^k

这是一个 等比数列 ，其中 n/2^k=1 时， k 的值就是总共缩小的次数，每次缩小操作只涉及两个数据的大小比较，所以，经过 k 次区间缩小操作，时间复杂度为 O(k)。通过 n/2^k=1，可以求得 k = log2^n ，所以时间复杂度就是 O(logn)。

O(logn) 对数时间复杂度

这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效。为什么这么说呢？因为 logn 是一个非常“恐怖”的数量级，即便 n 非常非常大，对应的 logn 也很小。比如 n 等于 2 的 32 次方， n 大约是 42 亿。也就是说，如果我们在 42 亿个数据中用二分查找一个数据，最多需要比较 32 次。

在用大 O 标记法表示时间复杂度的时候，会省略掉常数、系数和低阶。

对于常量级时间复杂度的算法来说，O(1) 有可能表示的是一个非常大的常量值，比如 O(1000)、O(10000)。所以，常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高。反过来，对数相对的就是指数。这也是为什么，指数时间复杂度的算法在大规模数据面前是无效的。

简单二分查找的递归与非递归实现

简单二分查找，是指在不存在重复元素的有序数据中查找值等于给定值的数据。

递归方式

递归是最容易想到的写法，它的好处就是代码清晰明了。思路：

首先找到「出口」，即退出方法的条件：1）如果mid正好是要找的target，那么直接返回即可；2）否则如果start>=end，则已经没有可能找到
找到参数变化的可能性，并区分不同可能性对参数以及递归的影响：1）如果a[mid]小于target，从mid+1为左边界继续找，end不变；2）如果a[mid]比target大，从mid-1 为右边界继续找，start不变

public int binarySearch(int srcArray[], int start, int end, int target) {
    if (start >= end) {
        return -1;
    }
    
    int mid = (end - start) / 2 + start;
    if (target == srcArray[mid]) {
        return mid;
    } else if (target > srcArray[mid]) {
        return binarySearch(srcArray, mid + 1, end, target);
    } else {
        return binarySearch(srcArray, start, mid - 1, target);
    }
}

这种方式叫做decrease and conquer，即不断缩小问题的范围，最终在某一个范围内寻找到结果，注意区分divide and conquer，这里是没有conquer的，所以前者的效率更高。

非递归方式

有了递归方式，将其转化为非递归就容易一些了，将递归的部分参数挪到循环外部定义，并以「全局」变量的形式参与计算，这样还节约了数据占用的空间，所以递归的方式的空间复杂度要高很多。

思路：

将递归拆解为while循环，找到「跳出条件」：start>end，此时已经找完所有可能，下标已经不再符合正常逻辑，直接退出
while内部的计算：每一轮只需要计算对应的变量的值并进行相同的比较逻辑即可，找到符合条件的直接退出

public int binarySearch(int srcArray[], int target) {
    int mid;
    int start = 0;
    int end = srcArray.length - 1;
    // 不断缩减start和end一直到相等，如果还找不到就退出，注意避免死循环
    while (start <= end) {
        mid = (end - start) / 2 + start;
        if (target < srcArray[mid]) {
            end = mid - 1; // 缩小范围，记得抛出去mid
        } else if (target > srcArray[mid]) {
            start = mid + 1; // 缩小范围，记得抛出去mid
        } else {
            return mid;
        }
    }
    return -1;
}

注意返回值为 -1 时的写法， while 中的条件是 start<=end 。

注意问题

关于mid的计算，并没有使用简单的(start+end)/2的方式，因为在两个值都是非常大的数字的时候加和是可能存在「溢出风险」的

start和end的更新问题，不能使用start=mid或end=mid，可能会导致死循环比如，当 high=3，low=3 时，如果 arr[3] 不等于 target，如果此时继续让high=mid或low=mid相当于条件没变，继续循环就会导致一直循环不退出。

这里只是最简单的二分查找，实际生产中，我们可能面对的是：

找出第一个值等于key的元素，或者找出最后一个值等于key的元素，甚至还有找出第一个<= 或者>=的元素位。

应用场景的局限性

此部分参考自ipine的blog，感谢她的精彩总结。二分查找的时间复杂度是 O(logn)，查找数据的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景有很大局限性。

1 . 二分查找依赖的是顺序表结构，即数组。二分查找不能依赖于其他数据结构，比如链表。主要原因是二分查找算法需要按照下标随机访问元素。数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。

2 . 二分查找针对的是有序数据。如果数据没有序，需要先排序。排序的时间复杂度最低是 O(nlogn)。所以，如果针对的是一组静态的数据，没有频繁地插入、删除，就可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。针对有频繁插入、删除操作的这种动态数据集合，二分查找是不适用的。要用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都很高。

3 . 数据量太小不适合二分查找。如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如在一个大小为 10 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多。只有数据量比较大的时候，二分查找的优势才会比较明显。

有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找。比如，数组中存储的都是长度超过几百的字符串，如此长的两个字符串之间比大小，就会非常耗时。为了尽可能地减少比较次数，二分查找就比顺序遍历更有优势。

4 . 数据量太大也不适合二分查找。二分查找依赖的是数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。二分查找是作用在数组这种数据结构之上的，所以太大的数据用数组存储就比较困难，就不能用二分查找了。

Q. 若二分查找依赖于链表结构，时间复杂度如何分析？

假设链表长度为 n，二分查找每次需要找到中间点，那么总共需要移动的指针次数为：

n/2 + n/4 + n/8 + … + 1

这也是一个「等比数列」，根据等比数列求和公式 (S = (a1-an*q)/1-q, q为公比, 且不为1)，其和等于 n-1 。所以最后算法时间复杂度为 O(n)。时间复杂度和顺序查找时间复杂度相同，但是，在二分查找的时候，由于要进行多余的运算，严格来说，会比顺序查找时间慢。

变种：求范围

另外有一个问题就是上面的代码其实在遇到第一个符合条件的数字之后就退出了，如果我们的数组里面有大量重复的数字，并且想知道这个数字的下标范围该怎么做呢？其实，这个也是二分思路，但是逻辑需要做一定的调整。

这道题分享自hk029。

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found

in the array, return [-1, -1].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

题目中说要求时间复杂度为 O(logn) ，作为查找算法，还是有序数组，默认都应该考虑到使用二分查找。这里需要返回两个值：左边界和右边界，如果用传统的思路，会很容易找到一个符合条件的位置，但是这个位置的左侧和右侧到底还有没有相同的值呢？难道需要向左或向右一位一位继续判断吗？显然那样的时间复杂度是 O(N) ，所以需要使用二分的方式分别对左边界和右边界进行查找计算。

左边界计算

先计算左边界，确定了最左侧的边界后再往右侧计算就容易很多了，而如何确定最左边界而不会导致左侧还有符合条件的数？需要对传统的二分计算规则做一定的调整：

Rule 1. A[mid] < target ，这时候说明还可以向右，st = mid+1
Rule 2. A[mid] > target ，这时候说明应该在左边，ed = mid-1
Rule 3. A[mid] == target ，这时候既可以左移，也可以不移动，ed = mid

考虑下面几种情况，假设 target=5：（在两个数的情况下mid = st）

case 1: [3 5] (A[st] < target = A[ed])

case 2: [5 7] (A[st] = target < A[ed])

case 3: [5 5] (A[st] = target = A[ed])

case 4: [3 7] (A[st] < target < A[ed])

case 5: [3 4] (A[st] < A[ed] < target)

case 6: [6 7] (target < A[st] < A[ed])

case1就是Rule1的情况，st = mid + 1就行。对于case2-3这时候，我们只要 ed = mid就行了，其实也就是把Rule 2 和Rule 3合并成了：

Rule 2*. A[mid] >= target， ed = mid

所以case 1-3 最后停止条件都是A[st] = A[ed] = target 对于case 4-6 都是A[st] != target，可以直接退出

右边界计算

已经找到了左边界，右边界的计算已经有了新start，则计算start和end之间的部分即可。还有一点要注意，此时范围内的数值都是>=target的。这里，我们让mid偏向右边mid = (st + ed)/2 + 1;然后主要控制ed移动就可以了。

代码

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int [] result = new int [2];
        result[0] = result[1] = -1;
        if(nums.length == 0)
            return result;

        int start = 0, end = nums.length-1, mid;
        
        // 寻找左边界
        while(start < end) { // 这里没有=的条件，在跳出后做逻辑
            mid = (end - start) / 2 + start;
            if (nums[mid] < target) { //保证start不会越过任何等于target的数
                start = mid + 1;  // 缩小左侧范围，排除不符合条件的数
            } else {       
                // 1.如果大于，将end移动到mid，缩小右侧范围，排除不符合条件的数
                // 2.如果等于，此时不能跳出，因为左侧仍然可能包括符合条件的数，所以必须移动end，此处移动到mid
                end = mid; // 不会发生死循环
            }
        }
        
        // 此时start==end，如果不为target则退出
        if(nums[start] != target)
            return result;
        result[0] = start; // 赋值而不是引用，所以start后面可以改变值
        
        // 寻找右边界
        end = nums.length-1; // 调整end为最大位置
        while(start < end) {
            mid = (end - start) / 2 + start + 1; //这里用+1是为了让mid偏向右边
            if(nums[mid] > target) {
                end = mid-1; // 缩小右侧范围，排除不符合条件的数
            }
            else { //因为start已经确定了，所以这里实际上不会出现比target小的数了，这里实际就是A[mid] == target
                start = mid; // 将start往右移动，start和result[0]之间的数都是符合条件的数，继续在和end之间的空间找右边界
            }
        }
        // 此时start==end，因为start初始值是合法的，这里直接赋值end给result即可
        result[1] = end;
        return result;
    }
}

变种：搜索旋转排序数组

LC原题33，要求时间复杂度为 O(logn)，暗示我们可以使用二分查找。

注：下面的思路和代码来自 VoidSky 的 gitbook，感谢他的分享。

思路

这个问题是二分查找的变种，它这里唯一的一个小trick就是把本来有序的数组做了一个旋转。但是注意，旋转的2部分是分别有序的。

还有一个很重要的特点：后半部分小于前半部分，所以其实很容易判断出 mid 在哪一部分。如果num[mid] > num[0]，我们就知道 mid 在左部分，否则在右部分。

这里不能直接用二分的问题在于：如果target和mid不在同一部分，就会出错。

举例nums: [4,5,6,1,2,3,4]，st = 0 ， ed = 6，mid = 3, target = 6

此时：mid 指向1，而 target 是6，说明 mid 和 target 不在同一部，会出现什么问题呢？

按照算法：

if (nums[mid] < target) 
    st = mid+1

这里，明明应该往左搜索，但是却往右边搜索了。所以，为了解决这个问题。我们可以引入 inf 和 -inf 。

引入inf和-inf

为了更加方便理解，我们举例：

我们随便看一个数组num:[4,5,6,1,2,3,4]

假设我们查询的目标是3：那我们实际查询的是右一段：[4,5,6,1,2,3,4]，实际上我们可以把前面的数都看作-inf：[-inf,-inf,-inf,1,2,3,4]
假设我们查询的目标是5：那我们实际查询的是左一段：[4,5,6,7,1,2,3,4]，实际上我们可以把后面的数都看作inf：[4,5,6,inf,inf,inf,inf]

这样其实就和普通的二分一样了。

如何知道在哪一段？

1.如果target < nums[0]和nums[mid]<nums[0]同时成立，那么我们按照普通的二分查找操作就行。

2.如果target < nums[0]和nums[mid]<nums[0]不同时成立，那么说明 target 和 mid 在不同部分。我们需要根据 target 的情况引入 inf 和 -inf ：

如果target < nums[0]，说明在右部，我们引入-inf，让mid值小于target，好让st向右移动，逼近target
否则，说明在左部，我们引入inf，让mid值大于target，好让ed向左移动，逼近target

代码

public class Solution {
    public int search(int[] nums, int target) {
        int st, ed, mid;
        st = 0;
        ed = nums.length - 1;
        while(st < ed){
            mid = st + (ed - st)/2;
            //增加部分
            int tmp = (nums[mid] < nums[0]) == (target < nums[0])
                   ? nums[mid]   // 如果在同一部分，则用原值
                   : target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE; // 否则根据情况引入-inf或inf

            if(tmp < target)
                st = mid + 1;
            else if(tmp > target)
                ed = mid;
            else
                return mid;
        }
        return nums[st] == target ? st : -1;
    }
}

一种递归的实现，思路比较清晰，通过判断mid的值比high是否小，小则右侧一定是升序，左侧不一定升序序，大概率升序+小于的升序序。如果mid的值比high大，则左侧一定升序，右侧不一定是升序，大概率升序+小于的升序。

对于升序+小于的升序，跟我们最开始处理的问题是一样的，所以一直用递归即可，最后到3个数的时候，一定是左侧有序和右侧有序的，结果也就找到了。所以它和普通的二分查找没有本质区别，只不过在判断向左侧还是向右侧寻找的判断上有独特的逻辑。

class Solution {
    public int search(int[] nums, int target) {
        return search(nums, 0, nums.length - 1, target);
    }
    
    private int search(int[] nums, int low, int high, int target) {
        if (low > high)
            return -1;
        int mid = (low + high) / 2;
        if (nums[mid] == target)
            return mid;
        if (nums[mid] <= nums[high]) {// 右侧有序
            // 这里已经是正常有序
            if (nums[mid] < target && target <= nums[high])
                return search(nums, mid + 1, high, target);
            else
                // 这里的范围不一定是有序的
                return search(nums, low, mid - 1, target);
        } else {// 此时的范围尾部小于前部，不是整体有序
            // 这里已经是正常有序
            if (nums[low] <= target && target < nums[mid])
                return search(nums, low, mid - 1, target);
            else
                // 这里的范围一定不是有序的
                return search(nums, mid + 1, high, target);
        }
    }
}

References

https://ipine.me/2018-11-08/
https://hk029.gitbooks.io/leetbook/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/034.%20Search%20for%20a%20Range[M].html

本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.

About Binary Search Algorithm