二分查找学习和解题

二分查找（Binary Search）是一种在 有序数组 中查找某一特定元素的搜索算法。

原理

首先我们用 low 和 high 定义要搜索的区域。然后取它们的中间值 mid 作为索引得到 arr[mid]，此时我们得到了两个区间：[low, mid], [mid, high]。将它与我们的目标数值 target 进行比较。

如果 arr[mid] 比 target 大，说明 target 不在 [mid, high] 区间，反过来说就是在 [low, mid - 1] 区间，接下来继续在这个新得到的区间中查找；同样，如果 arr[mid] 比 target 小，说明 target 在 [mid + 1, high] 区间；如果相等，说明找到，返回 mid 值。

二分查找的原理并不复杂，就是不断地将数组一切为二，直到找到为止，或切到区间长度为 1 为止。

实现

经典的二分查找，一般是对有序无重复元素的数组进行查找。下面是二分查找的 TypeScript 实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

const binarySearch = (arr: number[], target: number): number => {
  let low = 0
  let high = arr.length - 1
  let mid: number
  while(low <= high) {
    mid = low + Math.floor((high - low) / 2)
    if (arr[mid] > target) {
      high = mid - 1
    } else if (arr[mid] < target) {
      low = mid + 1
    } else {
      return mid
    }
  }
  return -1
}

low + Math.floor((high - low) / 2) 为 Math.floor((low + high) / 2) 的防溢出写法，low + high 有超出数值类型范围导致溢出的风险。此外因为 JavaScript 仅支持双浮点数的数值类型，所以需要做向下取整处理。如果是支持整数类型的编程语言，对于相除得到的值会丢弃小数部分，则不需要进行特殊处理。

需要注意的是，循环条件为 low <= high，而不是 low < high。这是因为要处理区间长度为 1 的情况，即 low 和 high 指向同一个位置的情况。

我们将相等的判断放置于条件分支的最后，是因为相等的概率比较低。设计算法时如果有多个判断条件，我们应把概率低的条件放在后面，这样能减少不必要的判断，尤其是这个比较需要复杂计算的情况。

如果 target 有不小概率完全不在数组范围内，你可以在函数的开头加下面这一行：

1

if (arr.length == 0 || target < arr[0] || target > arr[arr.length - 1]) return -1

时间复杂度为 O(logn)，这是二分法这么受欢迎的原因，不管数组有多大，每次进行二分直接去掉一半，效率是很高的。

二分查找的变形

二分查找的实现并不难，但是实际开发中，我们会用到的是二分查找的变形，其中细节很多，能够一次就写成正确的二分查找变形并不容易。下面我们找几道 leetcode 的算法题打打牙祭。

首先我们看一道 esay 题：69. x 的平方根。在不使用 sqrt 函数的情况下，求一个非负整数的平方根，保留整数部分

最直接的思路，是从 0 往上遍历，将与自身相乘得到的值与 x 比较。时间复杂度是 O(n)。其实我们可以换个思路，x 的平方根必然在 [0, x] 的范围内，这个范围其实就是一个 0 到 x 的有序数组，这符合二分法的特征。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

var mySqrt = function (x) {
  let low = 0;
  let high = x;
  let mid, product;
  while (true) {
    mid = Math.floor((low + high) / 2);
    product = mid * mid;

    if (product > x) {
      high = mid - 1;
    }
    else if { // 乘积小于 x
      if ((mid + 1) * (mid + 1) > x) return mid
      else low = mid + 1
    } else {
      return mid;
    }
  }
};