二分查找:为什么程序员都爱它？

假设你玩一个猜数字游戏。

我在心里想了一个 1-100 之间的整数,你来猜。每次猜完,我只告诉你"高了"还是"低了"。

你会怎么猜？

新手的思路

新手通常这样：

"是 1 吗？" → 低了
"是 2 吗？" → 低了
"是 3 吗？" → 低了
...

从 1 开始,一个一个往上试。运气好的话,几次就中;运气不好,猜 99 次。

这就是线性查找（Linear Search）。

最坏情况：要猜 100 次。

老手的套路

老手会这样：

"是 50 吗？" → 高了
"是 25 吗？" → 低了
"是 37 吗？" → 低了
"是 43 吗？" → 高了
"是 40 吗？" → 高了
"是 38 吗？" → 低了
"是 39 吗？" → 对了!

每次都猜中间值,根据"高了"还是"低了",直接排除一半的可能性。

这就是二分查找（Binary Search）。

最坏情况：只需要 7 次（log₂100 ≈ 6.64）。

从线性到二分：质的飞跃

让我们用一个更实际的例子。

场景:查字典

假设你要查"斑马"这个词。字典有 10000 个词条。

线性查找

从第一页开始,一页一页翻:

第1页：爱情 ❌
第2页：安全 ❌
第3页：暗号 ❌
...
第500页：斑马 ✅

找到了！但花了 500 次翻页。

二分查找

直接翻到中间：

第5000页：森林 → 太后面了
第2500页：海洋 → 还是后面
第1250页：电脑 → 再往后
第1875页：封面 → 还要后
第2187页：横竖 → 还往后
...（大约翻10次）
第500页：斑马 ✅

找到了！只花了 10 次左右。

500 次 vs 10 次 —— 这就是二分查找的威力。

二分查找的本质

核心思想

每次排除一半的可能性。

听起来简单,但这背后有个前提：

数据必须是有序的。

你不能在一本乱序的字典里用二分查找,因为你不知道目标在左边还是右边。

时间复杂度推导

假设数组有 n 个元素。

第 1 次：n → n/2（排除一半）
第 2 次：n/2 → n/4（再排除一半）
第 3 次：n/4 → n/8（继续排除）
...
第 k 次：n/2^k → 1（找到了）

当 n/2^k = 1 时,k = log₂n。

所以二分查找的时间复杂度是 O(log n)。

数据量增长 100 倍,二分查找只增加约 7 次操作。

代码实现

JavaScript 版本

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  
  while (left <= right) {
    // 找中间位置
    const mid = Math.floor((left + right) / 2)
    
    if (arr[mid] === target) {
      return mid  // 找到了
    } else if (arr[mid] < target) {
      left = mid + 1  // 目标在右边
    } else {
      right = mid - 1  // 目标在左边
    }
  }
  
  return -1  // 没找到
}

// 测试
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
console.log(binarySearch(arr, 7))   // 3
console.log(binarySearch(arr, 15))  // 7
console.log(binarySearch(arr, 8))   // -1

代码详解

1. 初始化左右指针

let left = 0
let right = arr.length - 1

left 和 right 定义了搜索区间 [left, right]。

2. 循环条件

while (left <= right)

注意这里是 <=,不是 <。

因为当 left === right 时,区间 [left, right] 里还有一个元素需要检查。

3. 计算中间位置

const mid = Math.floor((left + right) / 2)

为什么用 Math.floor？

因为 JavaScript 的除法是浮点数,我们需要整数索引。

小心溢出！

在某些语言（如 Java/C++）中,(left + right) 可能溢出。

更安全的写法：

const mid = left + Math.floor((right - left) / 2)

4. 比较和移动指针

if (arr[mid] === target) {
  return mid  // 找到了
} else if (arr[mid] < target) {
  left = mid + 1  // 目标在右半边
} else {
  right = mid - 1  // 目标在左半边
}

这是二分查找的核心逻辑：

• 如果中间值等于目标,直接返回
• 如果中间值小于目标,说明目标在右边,移动 left
• 如果中间值大于目标,说明目标在左边,移动 right

常见变体

1. 找第一个等于目标的位置

数组中可能有重复元素：

[1, 2, 3, 3, 3, 4, 5]

找第一个 3 的位置（应该返回 2）。

function binarySearchFirst(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    
    if (arr[mid] === target) {
      result = mid      // 记录位置
      right = mid - 1   // 继续往左找
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  
  return result
}

关键点：找到目标后,不直接返回,而是继续往左搜索。

2. 找最后一个等于目标的位置

function binarySearchLast(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    
    if (arr[mid] === target) {
      result = mid      // 记录位置
      left = mid + 1    // 继续往右找
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  
  return result
}

3. 找第一个大于等于目标的位置

这个在实际开发中很常用,比如找"版本号大于等于 1.2.0 的第一个版本"。

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

注意：

• 这里 right 初始化为 arr.length,不是 arr.length - 1
• 循环条件是 left < right,不是 left <= right
• 搜索区间变成了 [left, right)

面试高频问题

Q1: 二分查找一定比线性查找快吗？

不一定。

如果数组只有 10 个元素,二分查找最多 4 次,线性查找平均 5 次,差别不大。

但如果数组有 100 万个元素：

• 二分查找：最多 20 次
• 线性查找：平均 50 万次

数据量小时,差别不明显;数据量大时,天差地别。

Q2: 为什么面试爱考二分查找？

三个原因：

1. 代码短,但细节多
   只有十几行代码,但容易写错：
   • left + 1 还是 mid？
   • <= 还是 <？
   • 边界如何处理？
2. 考察基础
   涉及数组、循环、条件判断,是编程基础的集大成者。
3. 应用广泛
   很多问题都可以转化为二分查找：
   • 在旋转数组中查找
   • 求平方根（二分答案）
   • 找峰值元素

Q3: 递归版本怎么写？

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1  // 没找到
  }
  
  const mid = Math.floor((left + right) / 2)
  
  if (arr[mid] === target) {
    return mid
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right)
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1)
  }
}

递归 vs 循环：

实战应用

1. LeetCode 35: 搜索插入位置

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

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

// 测试
console.log(searchInsert([1,3,5,6], 5))  // 2
console.log(searchInsert([1,3,5,6], 2))  // 1
console.log(searchInsert([1,3,5,6], 7))  // 4

这就是我们前面讲的"找第一个大于等于目标的位置"。

2. LeetCode 69: x 的平方根

实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。

function mySqrt(x) {
  if (x === 0) return 0
  
  let left = 1
  let right = x
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    const square = mid * mid
    
    if (square === x) {
      return mid
    } else if (square < x) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  
  return right  // 返回 right,因为要向下取整
}

// 测试
console.log(mySqrt(4))   // 2
console.log(mySqrt(8))   // 2
console.log(mySqrt(16))  // 4

这里用二分查找的思路是：

答案在 1 到 x 之间,每次检查中间值的平方是否符合条件。

常见陷阱

陷阱 1: 死循环

// ❌ 错误写法
function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  
  while (left < right) {  // 注意这里是 <, 不是 <=
    const mid = Math.floor((left + right) / 2)
    
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] < target) {
      left = mid  // ❌ 错误: 应该是 mid + 1
    } else {
      right = mid - 1
    }
  }
  
  return -1
}

问题：当 arr[mid] < target 时,设置 left = mid 会导致死循环。

因为下一轮 mid 可能还是相同值。

正确写法：left = mid + 1

陷阱 2: 越界访问

// ❌ 错误写法
function binarySearch(arr, target) {
  let left = 0
  let right = arr.length  // ❌ 应该是 arr.length - 1
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    
    if (arr[mid] === target) {  // 可能访问 arr[arr.length]
      return mid
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  
  return -1
}

陷阱 3: 整数溢出

在 C++/Java 中：

// ❌ 错误: 可能溢出
int mid = (left + right) / 2;

// ✅ 正确
int mid = left + (right - left) / 2;

JavaScript 不用担心这个,因为有 BigInt。

小明的建议

1. 先理解思想,再背代码
   理解"每次排除一半"的思想,代码自然就能写出来。
2. 画图辅助
   用纸笔画出每一步 left、right、mid 的变化,更容易发现问题。
3. 区间定义要统一
   定义 [left, right] 还是 [left, right),全程保持一致。
4. 多刷变体题
   基础二分很简单,但变体题千变万化。多做几道才能融会贯通。
5. 面试时说出思路
   即使写不出完美代码,说出"二分查找"的思路也能得分。

总结

二分查找看似简单,其实是算法设计中"分而治之"思想的经典体现。

三个关键点：

1. 数据必须有序
2. 每次排除一半可能性
3. 时间复杂度 O(log n)

记住这个口诀：

左闭右闭用 <=,
左闭右开用 <,
mid 加一记心间,
边界处理别出错。

下一篇,我们会讲链表与数组的选择,敬请期待！

系列文章：

• 时间复杂度：从"这代码怎么这么慢"到"原来如此"
• 二分查找：为什么程序员都爱它？（本文）
• 数组 vs 链表：什么时候用哪个？（即将发布）

有问题？欢迎在评论区留言,小明会尽力回答！

冷笑话时间 🎭

面试官："你知道为什么二分查找这么快吗？"

程序员："因为它每次都砍掉一半工作量。"

面试官："那你知道为什么你加班这么多吗？"

程序员："因为需求每次都翻倍......"

面试官："......"

（完）