二分查找

基本概念

二分查找算法（Binary Search Algorithm），又称折半查找或对数查找，是一种在有序数组中高效定位目标元素的方法。其核心思想是每次将查找区间缩小一半，从而快速锁定目标位置。

算法步骤

1. 初始化：确定待查找的数据集合为有序数据
2. 设置查找区间：定义查找的左右边界，初始时left指向数组起始位置，right指向数组末尾位置
3. 计算中间下标：通过$mid=(left+right)/2$计算当前查找区间的中间下标mid
4. 比较并缩小区间：
   1. 如果$target==nums[mid]$,则找到目标，返回mid
   2. 如果$target<nums[mid]$,目标在左半区间，更新右边界right=mid-1
   3. 如果$target>nums[mid]$,目标在右半区间，更新左边界left=mid+1
5. 重复步骤3~4

算法思想

二分查找算法体现了经典的 「减而治之」 思想。

所谓 「减」，就是每一步都通过条件判断，排除掉一部分一定不包含目标元素的区间，从而缩小问题规模；「治」，则是在缩小后的区间内继续解决剩下的子问题。也就是说，二分查找的核心在于：每次查找都排除掉不可能存在目标的区间，仅在可能存在目标的区间内继续查找。

通过不断缩小查找区间，问题规模逐步减小。由于区间有限，经过有限次迭代，最终要么找到目标元素，要么确定目标不存在于数组中。

核心要点

二分查找 是一种在 有序数组 中高效查找目标元素的算法，其核心思想是 每次将查找区间缩小一半，从而快速定位目标位置。

算法特点

• 时间复杂度：O(log⁡n)，比线性查找 O(n) 更高效。
• 空间复杂度：O(1)，只需要常数级别的额外空间。
• 适用条件：数据必须是有序的（升序或降序）。
• 核心思想：减而治之，每次排除一半不可能的区域。

实现要点

1. 区间定义：使用左闭右闭区间 [left, right]。
2. 中间计算：mid = (left + right) // 2 或 mid = left + (right - left) // 2（防溢出）。
3. 边界更新：
   • 目标在右半区间：left = mid + 1
   • 目标在左半区间：right = mid - 1
4. 终止条件：left > right 时查找失败。

应用场景：

• 704二分查找1
• 374猜数字大小
• 35搜索插入位置