【算法面试】二分查找：如何在有序数组中高效搜索目标值

目录

题目描述

示例 1:

示例 2:

问题分析

解决方法

方法 1：标准二分查找

方法 2：递归二分查找

方法 3：非递归简化版本

方法 4：带调试信息的版本

详细步骤

总结

博主v：XiaoMing_Java

二分查找是一种常见的算法，广泛应用于计算机科学领域。它的原理是通过不断将目标区间对半划分，从而迅速缩小查找范围。这种方法非常适用于在有序数组中查找特定元素。本篇文章详细解析了如何在有序整型数组中使用二分查找算法来查找目标值，并提供多个代码示例来帮助理解。

题目描述

假设你有一个包含 n 个元素的升序整型数组 nums，以及一个目标值 target。你需要编写一个函数，在数组 nums 中搜索 target，如果目标值存在则返回其下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2

输出: -1

解释: 2 不存在 nums 中因此返回 -1

问题分析

二分查找法利用了数组已经排好序（升序）的性质，通过每次将查找范围缩小一半，从而极大地提高了查找效率。算法的核心思想如下：

1. 选择数组的中间元素作为比较对象。
2. 如果中间元素正好等于目标值，则直接返回该元素的下标。
3. 否则，如果目标值小于中间元素，则只需在左半部分继续查找；反之，则在右半部分查找。
4. 重复上述过程，直到找到目标值或查找范围为空。

解决方法

方法 1：标准二分查找

以下是实现二分查找的一种标准方法：

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left  target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

方法 2：递归二分查找

除了迭代方式，我们还可以采用递归方式实现二分查找：

public int search(int[] nums, int target) {
    return binarySearch(nums, target, 0, nums.length - 1);
}
private int binarySearch(int[] nums, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2; // 防止溢出
    int x = nums[mid];
    
    if (x == target) {
        return mid;
    } else if (x > target) {
        return binarySearch(nums, target, left, mid - 1);
    } else {
        return binarySearch(nums, target, mid + 1, right);
    }
}

方法 3：非递归简化版本

有时我们可以进一步简化代码，使其更简洁：

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left