二叉查找法

Question

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用 O(log n) 完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列）将 n 个元素分成个数大致相同的两半，取 a[n/2]与欲查找的 x 作比较，如果 x=a[n/2]则找到 x，算法终止；如 果 x<a[n/2]，则我们只要在数组 a 的左半部继续搜索 x；如果 x>a[n/2]，则我们只要在数组 a 的右 半部继续搜索 x。

常见问题是用来查找一个数字在有序数组中的索引位置。

如果该题目暴力解决的话需要 O(n) 的时间复杂度，但是如果二分的话则可以降低到 O(logn) 的时间复杂度。

遍历法 for 循环，时间复杂度 O(n)

var searchInsert = function (arr, x) {
  for (let i = 0, len = arr.length; i < len; i++) {
    if (arr[i] === x) {
      return i
    }
  }
  return -1
}

二分法，时间复杂度 O(logn)

var searchInsert = function (arr, x) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = (left + right) >> 1
    if (arr[mid] === x) { // x=a[n/2]
      return mid
    }else if (x < arr[mid]) { // x<a[n/2]
      right = mid - 1
    } else { // x>a[n/2]
      left = mid + 1
    }
  }
  return -1
}

二分查找法虽然简单，但写好它并没有那么容易，比如不能很好的判断边界条件，可能出现错误的结果或者出现死循环。

为了避免这些问题，我准备了一个通用的模板，方便记忆和使用。

function binary_search(left, right, check) {
  while (left < right) {
    // 选择左中位数
    let mid = (left + right) >> 1
    if (check(mid)) {
      // 先写可以排除中位数的逻辑
      left = mid + 1
    } else {
      // 右边不能排除
      right = mid
    }
  }
  // 退出循环的时候，单独处理额外的逻辑
  return left
}

首先把循环可以进行的条件写成 while(left < right) ，在退出循环的时候，一定有 left == right 成立，此时返回 left 或者 right 都可以，循环内只写两个分支，一个分支排除中位数，另一个分支不排除中位数。

关于模板需要这样使用：

function searchInsert(arr, x) {
  let left = 0;
  let right = arr.length - 1;
  let check = (mid) => x > arr[mid]
  let result = binary_search(left, right, check)
  if (arr[result] === x) {
    return result
  } else {
    return -1
  }
}

在这里补充一个小细节：除以 2 这件事情，还可以用右移 1 位来代替，位移运算的效率更高些，因为计算机更适合操作二进制。