前言

二分查找法是一种高效的查找算法，它的思想非常好理解，但编写正确的二分查找并不简单。本章从最基础的二分查找实现开始，讲解其编写技巧，接下来介绍它的四个常见变种的编写，最后应用二分查找来解决真正的面试题，学以致用的同时更加深对其的理解，真正掌握它。

什么是二分查找？

这是一种在有序的数组里快速找到某个元素的高效算法。例如第一章举过的例子：你借了一摞书准备走出书店，其中有一本忘了登记，如何快速找出那本书？你可以一本本的尝试，也可以每一次直接就检测半摞书，再剩下的半摞书依然重复这个过程，这样12本书，你只用4次即可。像这样每次将数据一分为二的进行查找的算法，就是二分查找法。

二分查找的局限性

虽然说查找的效率很高，跟所有的算法一样，也有其局限性。

1. 必须使用数组

需要借助数组通过下标访问元素只需要O(1)的特性。这一点链表就无法做到，因为访问某个元素必须要遍历，会徒增复杂度。

2. 数据必须是有序的

因为每次是与中间元素进行比较，结果是舍弃一半的查找范围，所以这个中间元素需要起到临界值的作用。

3. 数据量太小没必要使用

数据量太小，和遍历的速度区别不大，那就没必要使用二分查找。也有例外，如果比较操作很耗时，二分查找可以有效减少比较次数，即使数据量小也可以使用二分查找。

基础：二分查找的实现

每次我们拿顺序数组的中间值与需要查找的值进行比对，如果中间值比要查找的值大，就是小区间里查找，反之亦然。思路清楚后，那就上代码，跟着代码更好理解：

function binarySearch(arr, val) {
  let l = 0; // 左侧边界
  let r = arr.length - 1; // 右侧边界
  // 在[l ... r - 1]范围内查找
  
  while (r >= l) { // 终止条件
    const mid = (l + (r - l) / 2) | 0; // 取中间值
    if (arr[mid] === val) { // 正好找到了
      return mid; // 返回对应下标
    } else if (arr[mid] > val) { // 如果当前值大于查找值，去左边界找
      r = mid - 1; // 重新定义右边界，为mid - 1
    } else {
      l = mid + 1; // 重新定义左边界
    }
    
  }
  return -1; // 没找到返回-1
}

const arr = [1, 2, 3, 4, 5, 6, 9, 10];
binarySearch(arr, 10); // 7

这里，也包括之前章节的中间取值都是采用的l + (r - l) / 2 | 0方式，而没采用(r + l) / 2 | 0，是因为如果l和r都非常大，相加会出现整型溢出的bug。

首先需要得到mid，让数组以它为中心一分为二，左侧是[l ... mid - 1]小区间，右侧是[mid + 1 ... r]大区间。

因为是顺序数组，假如当arr[mid] > val时，就可以直接忽略大区间，要查找的值肯定在小区间里，所以让右侧的边界为r = mid - 1，这里为什么要- 1，因为之前的判断已经表明此时arr[mid]是不等于val的，所以需要将当前元素mid刨除在下次查找的范围内。反之亦然，每次查找都可以忽略一半的范围。直至最终l > r，表示没有找到。

注意开区间与闭区间的区别

为什么二分查找烧脑？根本原因在于它的边界问题，所以开头的时候要定义好边界的含义。

上面版本的二分查找使用的是闭区间定义，右侧边界的定义为r = arr.length - 1，也就是在[l ... r - 1]的范围内进行查找，所以循环的终止条件为r >= l，因为它们相等时数组里还有一个元素没有参与查找。

你也可以采用开区间的定义方式，也就是右侧边界为r === arr.length，在[l ... r )的范围内进行查找。此时循环的截止条件就不能是r >= l了，因为r作为下标存在数组越界的情况，条件需要调整为r > l。而且右侧边界的重新定义就不能是mid - 1了，右边界必须大于要查找元素的下标。开区间二分查找代码如下：

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length; // 开区间定义
  // 在[l ... r)范围内查找
  
  while (r > l) { // 注意结束条件
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] > val) {
      r = mid; // 重新定义不再 - 1
    } else {
      l = mid + 1;
    }
  }
  return -1;
}

所以书写定义好边界，以及熟悉它的含义，再写出准确无误的二分查找相信也不是难事。

递归版二分查找

其实递归版本的更好理解，因为子过程的重复性是一目了然的，只是性能会比循环略微差一丢丢，不过都是一个复杂度级别，区别很小。代码如下：

function binarySearch(arr, val) {
  const _helper = (arr, l, r) => {
    if (l > r) { // 因为是闭区间，相等时还有元素要比较
      return -1;
    }
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] > val) {
      return _helper(arr, l, mid - 1);
    } else {
      return _helper(arr, mid + 1, r);
    }
  };
  return _helper(arr, 0, arr.length - 1); // 使用闭区间
}

进阶：二分查找的变种

以上的二分查找是建立在数组里没有重复数据的情况下，但假如在一个重复数据的数组里，要返回第一个匹配的元素，上面实现的二分查找就不适应了。这也就是二分查找让人抓狂的变种问题，都需要在基础的二分查找上进行改造以满足需求，常见的有四种变种。

1. 查找第一个匹配的元素

这个查找规则是建立在已经找到了匹配的元素之后，因为是找到第一个，所以首先是判断这个元素是不是数组的第一个元素，然后是已经找到的元素的上一个元素是不匹配的才行。改造的代码如下：

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length - 1; // 闭区间
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] < val) {
      l = mid + 1;
    } else if (arr[mid] > val) {
      r = mid - 1;
    } else { // 如果已经找到了匹配的元素
      if (mid === 0 || arr[mid - 1] !== val) { 
        // 是数组第一个或前面的元素不匹配，表示找到了
        return mid;
      } else {
        // 否则上一个元素作为右区间继续
        r = mid - 1
      }
    }
  }
  return -1;
}

const arr = [1, 2, 2, 2, 2, 3, 4];
binarySearch(arr, 2) // 1

2. 查找最后一个匹配的元素

跟上一个变种类似，在找到了匹配的元素之后，需要判断这个元素是不是数组的最后一位，还需要判断匹配元素的后一位是不匹配的才行，改造代码如下：

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length - 1; // 闭区间
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] < val) {
      l = mid + 1;
    } else if (arr[mid] > val) {
      r = mid - 1;
    } else { // 如果已经找到了匹配的元素
      if (mid === arr.length - 1 || arr[mid + 1] !== val) {
        // 是数组最后一个元素或它的后面的不匹配
        return mid;
      } else {
        // 否则下一个元素作为左区间继续
        l = mid + 1
      }
    }
  }
  return -1;
}

const arr = [1, 2, 2, 2, 2, 3, 4];
binarySearch(arr, 2); // 4

3. 查找第一个大于等于匹配的元素

需要在已经找到的大于或等于的位置进行判断，如果这个元素是第一个或它前面的元素是小于要匹配的元素时，说明已经找到了。代码如下：

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length - 1; // 闭区间
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] >= val) { // 已经找打了大于或等于的元素
      if (mid === 0 || arr[mid - 1] < val) { 
      // 如果是数组的第一个元素或它的前面的元素不匹配 
        return mid;
      } else {
        r = mid - 1; // 缩小右边界
      }
    } else {
      l = mid + 1;
    }
  }
  return -1;
}

const arr = [1, 5, 5, 7, 8, 9];
console.log(binarySearch(arr, 4)); // 1

4. 查找最后一个小于等于匹配的元素

和上一个变种问题类似，重写小于或等于的元素集合即可，代码如下：

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length - 1; // 闭区间
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] >= val) { // 已经找打了大于或等于的元素
      if (mid === 0 || arr[mid - 1] < val) { 
      // 如果是数组的第一个元素或它的前面的元素不匹配 
        return mid;
      } else {
        r = mid - 1; // 缩小右边界
      }
    } else {
      l = mid + 1;
    }
  }
  return -1;
}

const arr = [1, 2, 2, 7, 8, 9];
console.log(binarySearch(arr, 5)); // 2

实践：求解力扣真题

你以为写出上面几个二分查找法就算掌握了么？真正二分查找的题目细节更讲究，来感受下二分查找为什么让人抓狂吧。

35 - 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 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

这题的示例已经描述的很清楚了，如果正好右这个元素，就返回这个元素的下标。有序、查找、无重复，这些关键词完全就是为二分查找量身定做，不过有一点和常规的二分查找不同，没有这个元素时返回前一个元素的下标，代码如下：

var searchInsert = function (nums, target) {
  let l = 0;
  let r = nums.length - 1;
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (target > nums[mid]) {
      l = mid + 1;
    } else if (target < nums[mid]) {
      r = mid - 1;
    } else {
      return mid; // 如果等于那就正好
    }
  }
  return l; // 否则返回左侧元素
};

540 - 有序数组中的单一元素

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例1：
输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例2：
输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

如果是使用暴力解法，那这道中等的题目就太简单了，最后的注意里面有强调，要保证这个解法在O(logn)级别。题目有交代是有序数组，所以这题很自然会想到使用二分查找法，不过上面写的二分查找好像不适用，麻烦的地方在于怎么确定要查找的元素在哪一边，如何每次抛一半不需要使用的数据。

经过观察，这数组有个特征，长度是奇数，因为只有一个数出现一次，其他数都出现两次。还有就是即使是都是奇数，如果按中间下标均分，它又分为两种情况：

1. 分割后两侧的数组长度为奇数

例如数组长度为7的数组被均分为两个长度3的数组，此时我们要把两个相同的数字作为一个数字处理。这里又分为两种情况：

1.1 - 中间元素与前一个相同，此时唯一不同的那个元素必然是在右侧，左侧是可以忽略的，而且下一次开始的下标从mid + 1开始即可。

1.2 - 中间元素与后一个相同，唯一不同的那个元素必然是在左侧，右侧可以忽略，且下一次截止的位置为mid - 1。

2. 分割后两侧的数组长度为偶数

此时还是分为两种情况来处理，与之前分割为奇数的恰恰相反：

2.1 - 中间元素与前一个元素相同时，唯一不同的那个元素在左侧部分，因为既然都是偶数，哪边有相同的元素，哪边就是奇数数组了，下一次查找截止的位置为mid - 2。

2.2 - 同理，中间元素与后一个元素相同，唯一不同的元素就在右侧，而且下一次开始的位置为mid + 2。

知道了怎么均分数组，也知道了边界怎么重定义，这个解法就很容易写出来了。不过还有一个注意点就是，当数组里只能一个元素的时候就不用比较了，必定是那个元素。完整代码如下：

var singleNonDuplicate = function (nums) {
  let l = 0;
  let r = nums.length - 1;
  while (r > l) { // 闭区间保留最后一个元素
    const mid = (l + (r - l) / 2) | 0;
    const splitIntoEven = (mid - l) % 2 === 0; // 分割后是否是偶数长度
    if (nums[mid] === nums[mid + 1]) { // 如果与前一个相同
      if (splitIntoEven) { // 而且左右是偶数长度
        l = mid + 2; // 符合2.2的情况
      } else {
        r = mid - 1; // 符合1.2
      }
    } else if (nums[mid] === nums[mid - 1]) { // 与后一个相同
      if (splitIntoEven) { // 是偶数长度
        r = mid - 2; // 符合2.1
      } else {
        l = mid + 1; // 符合1.1
      }
    } else {
      return nums[mid]; // 当前元素和前后都不相同，返回这个异类
    }
  }
  return nums[l]; // 返回最后一个元素
};

436 - 寻找右区间

有一个二维数组，里面每一个单独的数组i都表示的是一个区间值，第一个元素是该区间的起始点，
第二个元素是该区间终点。问是否有另一个区间j，它的起始点大于或等于区间i的终点，
这样的区间可以称j是i的右区间。

对于每一个区间i，你需找到它的下标值最小右区间，如果没有则返回-1。

注意:
你可以假设区间的终点总是大于它的起始点。
你可以假定这些区间都不具有相同的起始点。

示例 1:
输入: [ [3,4], [2,3], [1,2] ]
输出: [-1, 0, 1]

解释:
对于[3,4]，没有满足条件的“右侧”区间。
对于[2,3]，区间[3,4]具有最小的“右”起点;
对于[1,2]，区间[2,3]具有最小的“右”起点。

对于每一个区间i，需要找到另外一个区间j，这个j的起始点要大于等于i的终点。但是这样的区间可能会有多个，我们需要找到符合这个要求且下标值最小的那一项。

我们使用排序即可，按照起始点从升序排列，依次遍历时，符合条件的第一项，绝对就是下标值最小的那一项。但此时会遇到另外一个问题，就是排序之后的下标和最初的下标不同，此时我们可以使用map记录下最初的下标值。找到符合的区间后，查看该区间最初的下标，添加到返回的集合里即可。代码如下：

var findRightInterval = function (intervals) {
  const res = []; // 最终返回的结果
  const map = new Map(); // 记录最初的下标
  for (let i = 0; i < intervals.length; i++) {
    map.set(intervals[i], i); // 使用区间作为key
  }
  intervals.sort((a, b) => a[0] - b[0]); // 按照起始点升序排列

  for (let i = 0; i < intervals.length; i++) {
    let minIndex = -1;
    let l = i;
    let r = intervals.length - 1;
    while (r >= l) { // 闭区间，最后一个元素也要比较
      const mid = (l + (r - l) / 2) | 0;
      if (intervals[mid][0] >= intervals[i][1]) { // 如果符合
        minIndex = map.get(intervals[mid]); // 取得原始下标
        r = mid - 1 // 换小的起始点继续
      } else {
        l = mid + 1 // 不符合换大的起始点继续
      }
    }
    res[map.get(intervals[i])] = minIndex; 
    // intervals[i]是排序后所在的位置
    // 而map.get(intervals[i])找到的又是它原始的下标位置
    // minIndex对应的是其原始项的最小右区间
  }
  return res; // 返回集合
};

因为二分查找只能作用于有序的数组，所以数组无序时，我们可以先对其进行排序。如果不使用二分查找，第二层循环依然遍历，整体的复杂度就会变为O(n²)。

最后

本章我们手写实现了二分查找以及它的四个变种，对于如何书写正确的二分查找，也说明了定义边界时的开闭区间问题。还有就是当遇到有序、查找这两个关键词，很容易就能想到使用二分查找法先试试。如果是无序的呢？那就和最后一个题目一样，排序之后再找即可。