二分查找进阶 - 不仅仅是二分那么简单

这篇文章上次修改于 280 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

这是The-sword-of-algorithm项目二分查找系列的第二篇文章。
The-sword-of-algorithm这个项目专注提升前端爱好者的算法能力，本项目目前仅采用JavaScript实现所有内容。喜欢的话，欢迎Star关注一下。

回顾

在二分查找基础文章中，我们通过不断二分，移动双指针的位置缩小区间范围，直到两个指针左指针比右指针大的时候或者查找到目标元素的时候，才结束循环。这就是我们所谓的从循环中找答案的方法。

我们还可以有一种思路，那就是通过排除必定没有答案的区间来移动我们的范围，这个思路能够解决很多复杂的二分查找问题。

可以先尝试下这两道题：

二分排除

通过title应该也能看出来，二分排除的操作就是确定中间值（二分）与目标值的关系，排除必定没有目标值的区间即可。跟循环体中找答案的方法相反，我们不再是在缩短答案所在的区间，而是 排除必定没有答案的区间。

为什么笔者这么强调排除 必定没有 答案的区间，我们首先思考下使用二分排除我们的循环终止的条件是什么？

因为我们是不断排除没有答案的区间，所以我们没有找到目标值突出循环这么个逻辑，我们要一直循环到排除所有必定没有答案的区间，如果这个时候我们循环条件还是以left <= right 的逻辑循环的话，我们到最后无法判断区间移动也无法得到答案。所以我们二分排除的循环逻辑是left < right。这样的话能够保证删除所有的无答案区间以及确定答案的区间。现在不理解没关系，我们深吸口气心平气和继续往下看，一定会有收获的。

难以琢磨的条件分支

向下取整分支

现在我来解释一下为什么要各位注意排除必定没有答案的区间中的这个“必定”。设想一下，我们现在已经将区间缩小到只有两个元素了，我们有两种情况去结束这个循环。

首先我们来看看这个只有两个元素的区间的中间值会落在哪里：

const mid = Math.floor(left + (right - left)/2);  // Math.floor 进行向下取整

可以看到我们的mid就是我们的left。在这种情况下，假设判定的是mid右侧区间必定没有答案，那么它区间移动将是右指针移动，即：

right = mid;

这时候左右指针重叠，退出循环，排除所有无答案区间，确定答案。

回退一下，我们现在重新假设中间值的左侧，也就是mid所落在的区间必定没有答案，那么移动的就是左指针，即：

left = mid + 1;

这时候左右指针重叠，退出循环，排除所有无答案区间，确定答案。

向上取整分支

还是假设现在我们的区间缩小到仅有两个元素，这个时候会出现这样一种情况：通过题意判定left = mid。在这样一种判定逻辑下，我们会发现，出现无限循环了，left和right每次都不移动，一直卡在这里。

这个时候我们需要将我们的中间值取值进行调整：

const mid = Math.floor(left + (right - left + 1)/2);  // 通过加一实现向上取整

这个时候我们再来看看这个只有两个元素的区间，发现mid是与right一样的。这个时候如果中间值的右侧也就是mid所落在的区间必定没有答案的话，移动右指针，即：

right = mid - 1;

如果中间值的左侧必定没有答案的话，移动左指针，即：

left = mid;

可以发现两种情况都能够实现左右指针重叠从而推出循环确定答案。

笔者为什么要强调排除必然没有答案的区间原因也很明确了：究竟是向上取整还是向下取整其实我们不用纠结，只需要根据我们写的条件分支来判断即可。

left = mid + 1、right = mid 是采用向下取整
left = mid、right = mid - 1 是采用向上取整。

实战练习，巩固二分排除思想

搜索插入位置

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0

看到这题第一反应都是一次遍历解决问题，但是一看到这个是个排序数组，而且题目要明确是要查找某种条件的目标值，我们其实可以很自然地想到更有效率的二分查找。

既然是二分查找，首先我们要确定区间，以及初始区间的两端指针。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0,
        right = nums.length;
};

可以很自然地知道左指针一定是数组的首元素，也就是下标0。但是右指针我们需要稍加琢磨，笔者的习惯是在确定大体算法后，一定要先考虑一下极端情况（或者说特殊表现）。假设我们的target比这个数组的最后一个元素都要大，我们要返回的是尾元素的下标加一，也就是nums.length - 1 + 1。所以可以确定我们初始区间的右端是nums.length。

由于数组中的元素并不一定是目标元素，所以我们无法实现left <= right这个逻辑，因为在这个逻辑下我们结束循环的逻辑是nums[mid] === target。

所以这题自然而然地采用二分排除。我们将必不可能的区间一个个排除掉。

根据笔者刚刚说的方法，我们先中间值是向下取整const mid = Math.floor(left + (right - left)/2)，等到我们写完分支逻辑，看左右指针是怎么移动之后，再判断是否需要修改我们的中间值取法。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0,
        right = nums.length;
    
    while (left < right) {
        // 每次循环开始，先取一下中间值
        const mid = Math.floor(left + (right - left)/2);
        // 寻找必定不存在答案的区间，发现如果中间值小于 target, 则 `mid`以及其左侧都是不存在答案的区间
        if (nums[mid] < target) {
            left = mid + 1;       // [left，mid]这个区间都不存在，所以left移动到mid+1以缩小区间
        } else {
            right = mid;    
        }
    }
    // 因为是left = mid + 1逻辑，无需更改取整，直接下取整即可。循环结束，left === right === mid >= target
    
    return left;
};

我们再来看一到二分排除的极致体现：

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

这题如果用暴力遍历去解的话，这的简单得不得了。但是我们注意题目，时间复杂度需要控制在O(log n) 。

二分查找的时间复杂度就是O(log n) ，而且这题以及给定是一个升序数组（确定有序性，方便使用双指针确定范围），所以我们可以确定采用二分查找解题。接下来就是确定是采用循环体中找答案的方法还是二分排除的方法了。

还记得笔者刚刚说的一个习惯吗？确定大体算法后，一定要先考虑一下特殊表现。我们可以发现，这题最大的特点便是数组中的元素是重复的。如果采用循环体中找答案的方法去解，根本控制不了我们在相同目标值中的移动。但如果用二分排除的思想想一下，目标值其实是一个区间，区间的左端和右端其实是我们真正的目标值。对于相同元素区间的左端来说，其左侧必定没有相同元素。同理对于右端来说，其右侧必定没有相同元素。

所以确定思想是二分排除。

通过上述分析，我们可以知道要进行两次二分查找。所以我们先将主函数设计出来：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    // 通过 findFirst 函数查找目标值区间的左端
    let first = findFirst(nums, target);
    if (first === -1) {
        return [-1, -1];
    }
    
    // 通过 findLast 函数查找目标值区间的右端
    let last  = findLast(nums, target);
    return [first, last];
};

我们可以清晰地知道，如果目标区间的左端都找不到，那是不是就可以说明左端根本不存在。所以没有目标值直接返回[-1, -1] 终止查找。

我们来编写下我们的 findFirst函数

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number} 找到返回元素下标，找不到返回 -1
*/
function findFirst(nums, target) {
    // 首先确定初始区间的双端
    let left = 0,
        rigth = nums.length;
    
    // 采用二分排除
    while (left < right) {
        const mid = Math.floor(left + (right - left)/2);
        // 判断必不存在答案的区间，确定分支写法，从而判断是否调整取整
        if (nums[mid] < target) {
            left = mid + 1;   // nums[mid]如果小于target，则[left,mid]必定没有答案，移动left
        } else {
            right = mid;
        }
    }
    
    if (nums[left] === target) {
        return left;
    }
    return -1;
}

确定我们区间一定的写法是：left = mid + 1和right = mid ，所以采用下取整，无需更改mid取法。

我们再来编写一下findLast 函数：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number} 因为 findFirst 找到了，所以 findLast 不存在找不到的情况，最极端的就是只有一个目标值，左右端重叠
*/
function findLast(nums, target) {
    // 首先确定初始区间的双端
    let left = 0,
        rigth = nums.length;
    
    // 采用二分排除
    while (left < right) {
        // mid待更改，请看后面文字解析
        const mid = Math.floor(left + (right - left)/2);
        // 判断必不存在答案的区间，确定分支写法，从而判断是否调整取整
        if (nums[mid] > target) {
            right = mid -1   // nums[mid]如果大于target，则[mid,right]必定没有答案，移动right
        } else {
            left = mid;
        }
    }
    // 直接返回下标即可，走到这一步就说明findFist返回值是必定不为-1的，说明目标区间至少有一个元素
    return left;
}

我们发现这里的移动逻辑是right = mid - 1和left = mid，所以我们需要将mid的取值改为向上取整，即：

const mid = Math.floor(left + (right - left + 1)/2);

此题轻松解决~以下为完整代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let first = findFirst(nums, target);
    if (first === -1) {
        return [-1, -1];
    }
    let last  = findLast(nums, target);
    return [first, last];
};

function findFirst(nums, target) {
    let left = 0,
        right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor(left + (right - left)/2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    if (nums[left] === target) {
        return left;
    }

    return -1;
}

function findLast(nums, target) {
    let left = 0,
        right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor(left + (right - left + 1)/2);
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }

    return left;
}

笔者认为，写的这两篇二分查找的解题（上一篇地址：二分查找基础）思想真的可以对付基本上所有单纯二分的题了，只要能够有着清晰的思路一步步下来，跟玩一样。

接下来这个项目（The-sword-of-algorithm）的二分查找专题便只会更新题解了，二分思想的文章到这里就完结撒花啦。欢迎关注笔者的这个项目The-sword-of-algorithm 。

Uni