leetcode奇技淫巧-吃透“复杂”的二分查找

二分查找很简单？

简单？

虽然大家都说二分查找很简单，很基础，其实我一直觉得它并不简单，实际上如果是一个新手写二分查找，他会发现其中有非常多的情况要考虑到。那为什么我们把二分查找的题目写多了之后就觉得写二分查找很简单了呢？这是因为我们人脑比较容易记住模型场景，记住定式，虽然我们在刷 leetcode 的时候，题目中在二分的时候，各种情况我们不一定都去想过一遍，但是什么样的场景该用什么样的模型我们知道（刷题训练的结果），所以我们能很快写出来。所以我一直认为那些能力一般却总是说“简单”的人，连为什么“简单”这个本质都没有看清，这样的思维能力对于他们怎么可能简单呢？其实也只是不断训练得到的结果，当然并不是说训练不重要，训练固然重要，如果我们带有自己的总结和思考去刷那些并不简单的“简单”算法，将会使得训练的效益放大！

三个层面和四种定式

下面我们将会从三个层面来思考，编写多种样式的二分查找，编写的过程中我会去尝试考虑到所有边边角角的情况

哪三个层面呢？

• 层面一：考虑到循环内是否要把 mid 指向目标值这一条件独立出来
• 层面二：考虑到循环内是写成left = mid - 1还是写成left = mid
• 层面三：考虑到循环条件是写成left <= right，还是写成left < right

可以写成哪几个定式呢？

• 定式一：我们决定在循环中采用三种情况考虑，target == arr[mid]，target < arr[mid]，target > arr[mid]
• 定式二：我们决定在循环中采用两种情况考虑，target <= arr[mid]，target > arr[mid]或者target >= arr[mid]，target > arr[mid]
• 定式三：我们决定循环内直接将mid赋给left和right，而不是mid + 1和mid - 1赋给left和right
• 定式四：我们决定循环条件采用<而不是<=

模板题目

题目：已知一个从小到大的整型数组 arr，我们想找到目标值 target 在数组中的下标值，找到返回下标，找不到返回 -1

定式一

模板

public int function(int[] arr, target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        if (target > arr[mid]) {
            left = mid + 1;
        }
        else if (target < arr[mid]) {
            right = mid - 1;
        }
        else {
            return mid;
        }
    }
    return -1;
}

结论

• 如果数组中存在此目标值，那么 mid 总会遍历到该目标值上

  如果数组中不存在此目标值，那么 mid 总会遍历到目标值左右两个值上，且两个值都会被遍历到

• 如果数组中存在目标值，就会直接返回，若不存在才会通过循环出来

• 循环出来之后（只要出来就是无目标值），left 总比 right 大一，left 指向目标值临近的后一个元素，right 指向目标值临近的前一个元素

• left 可能等于数组长度，当且仅当目标值比数组最后一个元素还大的时候

  right 可能等于 -1，当且仅当目标值比数组第一个元素还小的时候

思考

• 为什么循环条件要写成<=而不是<？

  我们假设循环条件不包含等于，假如数组中部分序列是1,2,3,4,5，,2 假如是目标值，现在 mid 指向 3，目标值比 mid 指向的元素小，所以 right 要指向 2，left 不变指向 1，再循环，left 指向 2，right 指向 2，好，我们这个时候跳出循环，那么 left == right，并且，left 的后一个元素就是目标值。假如 3 是目标值，现在 mid 指向 2，目标值比 mid 指向的元素大，left 指向 3，right 依旧是指向 4，再循环后，可以直接 return 了，由如果 left 指向 3，right 指向的是 5，再循环后，left 指向 3，right 指向 3，循环出来，left == right，且 left 就是指向目标值。我们发现当循环条件写成<时候会有问题，无法确定 left 是指向目标值还是 left 的后面一个指向了目标值，如果我们改写成<=就可以成功避免这个问题，不信的同学可以照着这个思路尝试分析一下，发现是没问题的

• 如何理解若目标元素在数组中不存在，循环出来后 left 指向目标元素值的后一个元素，right 指向前一个？

  我们分析一下，假如1,2,3,4,5是数组中的一部分，现在目标值是 2.5，mid 成功指向了 3，那么现在 left 是 1，right 是 2，再循环后 left 和 right 都指向了 2，再循环后 left 指向了 2，right 指向了 3，ok，满足问题。假如 mid 指向的是 2 呢，那么 left 是 3，right 是 4，再次循环后，left 是 3，right 是 2，同样也满足问题，又如果 left 是 3，right 是 5，再次循环后，left 是 3，right 也是 3，再次循环后，left 是 3，right 是 2，还是满足问题，这样来看这个结论确实存在！

• 为什么存在 left 等于数组长度，right 等于 -1 的情况呢？

  我们想一下数组只有一个元素的极端情形，目标值比这个元素小或者大，就很好得出这个结论了

如何记忆

其实这种写法是本人最常用的二分查找的写法，写法如何记忆呢？结论又如何理解记忆呢？

• 写法记忆两个点：1.循环条件小于等于 2.循环内分三种情况。
• 结论记忆三个点：1.目标值存在一定会被 mid 遍历到然后 return 2.目标值不存，循环出来时，left 一般是目标值相邻的后一个元素，right 是前一个 3.存在 left 和 right 超过边界的情况

定式二

模板一

public int function(int[] arr, int target) {
    int left = 0. right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        if (target >= arr[mid]) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return right >= 0 ? (target == arr[right] ? right : -1) : -1;
}

结论

• 循环出来之后，left 总比 right 大一，若目标值存在，right 指向目标值，left 指向目标值后面一个元素

  循环出来之后，left 总比 right 大一，若目标值不存在，right 指向目标值前一个元素，left 指向目标值后面一个元素

• left 可能等于数组长度，当且仅当目标值比数组最后一个元素还大的时候

  right 可能等于 -1，当且仅当目标值比数组第一个元素还小的时候

模板二

public int function(int[] arr, int target) {
    int left = 0. right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left >> 1);
        if (target <= arr[mid]) {
            right = mid - 1
        }
        else {
            left = mid + 1;;
        }
    }
    return left < arr.length ? (target == arr[left] ? left : -1) : -1;
}

结论

• 循环出来之后，left 总比 right 大一，若目标值存在，left 指向目标值，right 指向目标值前面一个元素

  循环出来之后，left 总比 right 大一，若目标值不存在，left 指向目标值前一个元素，right 指向目标值后面一个元素

• left 可能等于数组长度，当且仅当目标值比数组最后一个元素还大的时候

  right 可能等于 -1，当且仅当目标值比数组第一个元素还小的时候

思考

• 为什么条件写成target >= arr[mid]循环出来时候 right 所指的是目标值？为什么条件写成target <= arr[mid]循环出来时候 left 所指的是目标值？

  首先循环条件是left <= right，意味着循环出来时候 right 一定在 left 前面一个元素。若存在1,2,3,4,5是数组中一部分，我们先看target >= arr[mid]这个条件，假如 mid 指向的是 target 3，那么 left 为 4，right 为 5，循环一次后，right 指向了 3，如果最开始 target 小于 mid 指向的值，循环多次后 right 总会移动到 target 上。所以最后出来的时候 right 指向的就是目标值。如果条件是target <= arr[mid]也可以这样分析。

如何记忆

这种写法其实也蛮常用的，这种定式也是必掌握的

• 写法记忆两个点：1.循环条件是小于等于 2.循环内只有两种情况
• 结论记忆两个个点，需要当场分析：1.若条件是target >= arr[mid]，假如 mid 指向了 target，通过循环最后总会让 right 指向目标值。若条件是target <= arr[mid]，假如 mid 指向了 target，通过循环最后总会让 left 指向目标值。2.left 和 right 可能超过界限

定式三

模板

public int function(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right - 1) {
        int mid = left + (right - left >> 1);
        if (target > arr[mid]) {
            left = mid;
        }
        else if (target < arr[mid]) {
            right = mid;
        }
        else {
            return mid;
        }
    }
    if (target == arr[left]) {
        return left;
    }
    else if (target == arr[right]) {
        return right;
    }
    return -1;
}

结论

• 循环出来后 left 总是比 right 小一，若 left 在数组最左边，则其有可能是目标值，若 right 在数组最右边，则 right 有可能是目标值
• 只要目标值不是在数组左右两端上，mid 都可以遍历到并且通过循环中的 return 返回
• left 和 right 都不可能超出数组界限

思考

其实这种写法很麻烦，一般不会写成left = mid和right = mid，因为非要这样写会将许多特殊的边边角角情况写进去，比较繁杂。我们来稍微分析一下

• 为什么循环条件是left < right - 1，而不是left <= right或者left < right？

  因为我们如果写成left < right或者left <= right会发现可能出现死循环，假设1,2,3,4,5是数组中一部分，target 是 2.5，现在 left 在 2，right 在 3，循环后 left 还是 2，right 还是 3，这样就造成了死循环，所以只能写left < right - 1

• 为什么循环结束后 left 或者 right 指向的元素可能是目标值？

  一个原因是循环条件是left < right - 1导致一个元素或者两个元素的数组没有考虑到所以要 left 和 right 都检查一遍，还有一个原因就是如果过目标值是数组最后一个元素，那么循环出来后 right 就有可能是目标值，如果目标值是数组第一个元素，那么循环出来后 left 就有可能指向目标值

如何记忆

这种写法还是平常少些，当然理解和思维过程还是走一遍为好，加深记忆，同时方便在写二分查找题目时候，遇到各种题型能够快速在脑中间建立各种各样的模型

• 写法记忆三个点：1.循环条件left < right - 1 2.循环内三种情况，且left = mid或者right = mid3.循环出来要判定 left 和 right 是否指向目标值
• 结论记忆两个点：1.一般情况 left 和 right 把目标值加在中间 2.当 left 是最左边时候，有可能出现 left 为目标值或者 left 左边才是目标值，right 同理

定式四

模板

public int function(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        if (target > arr[mid]) {
            left = mid + 1;
        }
        else if (target < arr[mid]) {
            right = mid;
        }
        else {
            return mid;
        }
    }
    return -1;
}

结论

• 只要目标值在数组中存在，mid 一定会遍历到
• 若循环出来，目标值不存在，left == right 并且指向目标值后面一个元素，可能超右界

思考

• 为什么 right 最开始是 arr.length 并且循环中是mid = right？

  因为我们把它理解成左闭右开区间就行了，如果理解成左闭右开本质上就是定式一的形式，所以我们写right = mid，实际上 right 指向的 mid 左边的一个元素了

• 为什么左开右闭不行？

  我们可以尝试一下 left 最开始等于 -1，right 最开始等于 arr.length - 1，我们分析一下运行过程，假如有1,2是数组中一部分，left 是 1，target 是 1.5，right 是 2，那么就会陷入死循环了，left 不断的找到 1。那如果我们最开始 left 等于 0，right 等于 arr.length - 1，但是循环内条件 left = mid，right = mid - 1 呢？同样也有可能陷入死循环。也就是说在循环条件是 left < right 的前提下，只要 left = mid 就有可能陷入死循环。所以目前只能使用左闭右开

如何记忆

其实这个定式我用的也不多

• 写法记忆一个点：1.左闭右开，模仿定式一
• 结论记忆两个点：1.若值存在，mid 一定可以遍历到然后通过 return 出来 2.若值不存在，循环出来，left 和 right 一定相等，并且是目标值后面一个元素，有可能超过右界

总结

本人一般常用定式一和定式二，一般题目都是在定式一的基础上修改一下，定式二对于一些题目还是挺方便的，定式三基本没用到过。其实定式二，定式三，定式四都是在定式一的情况下的拓展。