二分法介绍

发表于 | 分类于 |
字数统计: 291 字 | 阅读时长 ≈ 1 分钟

核心

  • 循环不变量原则，只有在循环中坚持对区间的定义
    确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。

方法的基础条件

  • 数组是有序数组

边界条件

  • 左闭右闭即[left, right]

    • while(left < right) right = middle

  • 左闭右开即[left, right)

    • while(left <= right) right = middle - 1

  • mid = left + (right - left) / 2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function search(arr, target) {
  let i = 0,
      j = arr.length - 1; // 定义target在左闭右闭的区间里，[i, j]
  while (i <= j) { // 当 i==j, [i, j]依然有效，所以用 <=
    let mid = i + (j - i) / 2; // 防止溢出 等同于(i + j)/2
    if (arr[mid] === target) {
      return mid; // 数组中找到目标值，直接返回下标
    } else if (arr[mid] > target) {
      j = mid - 1; // target 在左区间，所以[i, middle - 1]
    } else {
      i = mid + 1; // target 在右区间，所以[middle + 1, j]
    }
  }
  // 未找到目标值
  return -1;
}

复杂度

  • 时间复杂度：O(logn)
    其中 n 为数组的长度。二分查找所需的时间复杂度为 O(logn)

  • 空间复杂度：O(1)
    我们只需要常数空间存放若干变量