代码随想录算法训练营第1天｜数组Part01

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。 你必须编写一个具有 O(log n) 时间复杂度的算法。

LeetCode704. 二分查找

二分查找的前提条件

1. 数组有序
2. 无重复元素

若存在重复元素，返回的下标可能不唯一，可能需要额外逻辑处理

循环不变量原则

二分法的核心是：始终保持区间定义的一致性（即循环不变量）。

常见区间定义有两种：

1. 左闭右闭区间 [left, right]

• 循环条件：while (left <= right)
• 中点计算：const mid = left + ((right - left) >> 1)
• 边界收缩方式：
  • 若 nums[mid] > target：排除右侧 → right = mid - 1
  • 若 nums[mid] < target：排除左侧 → left = mid + 1

2. 左闭右开区间 [left, right)

• 循环条件：while (left < right)
• 中点计算：const mid = left + ((right - left) >> 1)
• 边界收缩方式：
  • 若 nums[mid] > target：排除右侧 → right = mid
  • 若 nums[mid] < target：排除左侧 → left = mid + 1

正确代码示例（左闭右闭区间）

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = left + ((right - left) >> 1); // 避免溢出，更高效
        if (nums[mid] === target) return mid;
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

关键总结

1. 区间定义决定一切：

   • [left, right] 对应 while (left <= right)
   • [left, right) 对应 while (left < right)

2. 始终保证循环内 mid 落在合法区间中

   • 推荐统一使用：mid = left + ((right - left) >> 1)

3. 防止死循环

   • 每次循环要收缩区间
   • 切忌写错为 right = mid（在 [left, right] 情况下会死循环）

4. 为什么向下取整？

   • 保证 mid 不越界
   • 保证区间逐步缩小
   • 提高计算效率（避免函数调用）