数组题解——二分查找【LeetCode】

704. 二分查找

算法逻辑分析

1. 初始化边界

   • left 设为0，right 设为len(nums)，表示左闭右开区间 [left, right)。
   • 这意味着搜索区间包含下标left，但不包含下标right。

2. 循环条件

   • while left < right:，只要left小于right，就一直循环。
   • 终止时，left == right，搜索区间为空。

3. 中点计算

   • mid = (left + right)//2，取当前区间的中间位置。

4. 比较并缩小区间

   • if nums[mid] < target:
     • 目标值在mid右侧，left = mid + 1。
     • 新区间为[mid+1, right)。
   • elif nums[mid] > target:
     • 目标值在mid左侧，right = mid。
     • 新区间为[left, mid)。
   • else:
     • 找到了目标值，返回mid。

5. 未找到目标值

   • 如果循环结束还没找到，返回-1。

核心点

• 左闭右开区间 [left, right)：这是这段代码的核心思想。每次区间调整都严格遵循这个规则，保证循环不变量（即任何时候区间外都不是目标）。
• 区间调整方式：
  • 小于目标时，left = mid + 1，排除mid。
  • 大于目标时，right = mid，排除mid右侧。
• 循环不变量保证：
  • 循环内始终有：nums[left-1] < target，nums[right] >= target（伪注释）。
• 终止条件：区间为空，说明不存在目标元素。

# 左闭右开
class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums)while left < right:# 循环不变量：# nums[left-1] < target# nums[right] >= targetmid = (left + right)//2if nums[mid] < target:left = mid + 1elif nums[mid] > target:right = midelse:return midreturn -1

复杂度分析

时间复杂度

• 每次循环将区间减半，最坏情况下要查找log2(n)次。
• 因此，时间复杂度为 O(log n)。

空间复杂度

• 只用常数级别的辅助变量（left, right, mid等）。
• 空间复杂度为 O(1)