LeetCode-704-二分查找

算法刷题>LeetCode
2.8k words

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1

你必须编写一个具有 O(log n) 时间复杂度的算法。

示例1：

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例2：

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

解题思路

将该题简化，我们会发现以下几个关键词：有序数组、无重复元素、O(log n)，这是一道很典型的二分查找，借由该题，我们将详细叙述二分的思想。

1. 二分查找的基本原理

二分查找（Binary Search）是一种基于分治策略的查找算法，其核心思想是通过不断将有序数据集对半分割来快速定位目标元素
。算法要求数据必须预先排序（通常为升序或降序），从而利用有序性快速缩小搜索范围。

数学基础​​：对于一个长度为n的有序数组，二分查找最多需要⌊log₂n⌋+1次比较
。例如，当n=1000时，最多只需10次比较即可完成查找，而线性查找可能需要1000次比较。这种指数级的效率提升使得二分查找在处理大规模数据时极具优势。

适用场景​​：

  • 数据结构支持随机访问（如数组、向量）
  • 数据必须有序（若无序需先排序）
  • 存在明确的判断条件（能确定目标在左半区还是右半区）

2. 二分查找的两种主要实现方式

2.1 左闭右闭区间 [left, right]

这是最直观的实现方式，搜索区间包含左右边界指向的元素。

​​算法流程​​：

​1.​初始化边界​​：设置左边界left = 0，右边界right = nums.length - 1

​2.​循环条件​​：当left ≤ right时继续查找（确保搜索区间有效），因为left == right是有意义的

​3. ​计算中间位置​​：mid = left + ((right - left)>>1)（防止整数溢出的安全写法，还涉及到符号运算顺序级）

​4.​比较与判断​​：

  • 如果arr[mid] == target，查找成功，返回mid
  • 如果arr[mid] < target，说明目标在右侧，更新left = mid + 1 （此时mid值一定不是目标值，那么接下来要查找的左区间结束下标位置就是 middle + 1，遵循区间左闭右闭）
  • 如果arr[mid] > target，说明目标在左侧，更新right = mid - 1

​​5.终止条件​​：如果循环结束仍未找到目标，返回-1表示查找失败

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1); // 防止溢出
            if(nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left =  mid + 1;
            else 
                right = mid - 1;
        }
        return -1;
    }
}

2.2 左闭右开区间 [left, right)

这种实现方式中，搜索区间包含左边界指向的元素，但不包含右边界指向的元素。

​​算法流程​​:

1.​初始化边界​​：设置left = 0，right = nums.length（右边界不包含）

2.循环条件​​：当left < right时继续查找（这里使用 < ,因为left == right在区间[left, right)是没有意义的）

3.​​计算中间位置

4.​比较与判断​​：

  • 如果arr[mid] == target，查找成功，返回mid
  • 如果arr[mid] < target，更新left = mid + 1
  • 如果arr[mid] > target，更新right = mid（注意不是mid-1），因为当前arr[mid]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为mid，即：下一个查询区间不会去比较arr[mid]

5.终止条件​​：循环结束时仍未找到目标，返回-1

​​代码实现​​：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution{
    public int search(int [] nums, int target){
        int left = 0;
        int right = nums.length;
        //有问题 int right = nums.length - 1; 
        while (left < right){
            int mid = left + ((right  - left) >> 1);
            if(nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else 
                right = mid;
        }
        return -1;
    }
}

2.3 两种实现方法对比

特性 左闭右闭区间 [left, right] 左闭右开区间 [left, right)
初始右边界 right = nums.length - 1 right = nums.length
循环条件 while (left <= right) while (left < right)
边界更新 (nums[mid] > target) right = mid - 1 right = mid
区间为空的条件 left > right left == right
mid 计算偏好（防死循环） mid = left + (right - left) / 2 或 mid = left + (right - left + 1) / 2 均可 必须使用 mid = left + (right - left) / 2（偏左）

3. 关键点总结

3.1 防止整数溢出

计算中间位置时，应使用left + (right - left) / 2而非(left + right) / 2，这样可以避免当left和right都很大时相加导致的整数溢出。

3.2 循环条件的选择

循环条件必须与区间定义保持一致。左闭右闭区间使用left <= right，因为当left等于right时区间仍包含一个元素；左闭右开区间使用left < right，因为当left等于right时区间为空。

3.3 边界更新的逻辑

边界更新必须确保每次迭代都能缩小搜索范围，同时不遗漏可能的目标元素。特别是在左闭右开区间中，当目标值小于中间值时，右边界更新为mid而非mid-1，因为右边界本身不指向待检查元素。