二分查找

定义

二分查找是一种在有序序列中高效查找目标值的算法。它每次取区间中点与目标比较，根据大小关系把查找范围折半，从而快速逼近结果。

原理

维护左右两个边界，计算中点 mid。若中点值等于目标则返回；若中点值小于目标则在右半区继续；若大于目标则在左半区继续。每次比较都将范围缩小一半，因此最多比较 log₂n 次。前提是数据必须有序。实现时需注意中点计算避免溢出、边界更新避免死循环。其变体可用于求上下界、旋转数组查找以及对答案二分。

复杂度

• 时间复杂度：O(log n)
• 空间复杂度（迭代）：O(1)
• 空间复杂度（递归）：O(log n)

应用场景

• 有序数组与索引中的快速查找
• 求满足条件的边界值
• 对单调答案进行二分（如最小化最大值）