二分查找的前提是什么？

有序、并且能按下标 O(1) 访问，才能二分。每次丢掉一半，时间是 O(log n)。链表不适合，因为走到中点已经是 O(n)。

原理

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

中点写成 left + (right - left) / 2，是为了避免两个很大的下标相加溢出。JavaScript 的安全整数范围内普通加法也够用，这个写法仍然更清楚。

循环条件用 left <= right 时，区间是闭区间，找不到就让 left 超过 right。改成 left < right 时，更新规则也要改，两套不要混。

找第一个大于等于目标的位置时，相等不立刻返回，而是把右边界收到 mid，循环结束后检查 left 是否还在数组里。

追问

旋转数组、边界题怎么想？

先判断哪一半是有序的，再看目标落不落在那一半。写完用空数组、一个元素、两个元素和目标在两端走一遍。

对象数组可以二分吗？

按某个已排序的键可以。键不唯一时要事先定义要的是最左还是最右。数据如果经常插入，保持有序的成本可能超过二分省下的查找。

易错点

• 死循环：更新边界时 right = mid 或 left = mid 却没有缩小区间。
• 没排序就二分。
• 中点用 (left + right) >> 1 时，负数下标会出问题。下标应当是非负的。

相关

• 复杂度
• 排序