1 题目描述

704. 二分查找要求实现一个二分查找算法，来在一个升序排列的整数数组中查找指定的目标值 target。如果找到目标值，则返回它的索引；如果没有找到，则返回 -1。

2 解题思路

二分查找是一种高效的查找方法，适用于已排序的数组。其基本思想是通过将目标值与数组中间位置的元素进行比较，来逐步缩小查找范围直至找到目标值或查找范围为空为止。

• 初始化：设定两个指针 l 和 r 分别指向数组的起始位置和结束位置。
• 循环条件：当 l <= r 时，继续查找。
• 中间位置计算：为了避免可能的最大整数溢出，我们使用 mid = l + (r - l) / 2 来计算中间位置。
• 比较并更新指针：
  • 如果 nums[mid] == target，则找到了目标值，返回 mid。
  • 如果 nums[mid] > target，则说明目标值在左侧子数组中，所以将右指针 r 更新为 mid（不包括 mid）。
  • 如果 nums[mid] < target，则说明目标值在右侧子数组中，所以将左指针 l 更新为 mid + 1。
• 终止条件：如果退出循环，说明没有找到目标值，返回 -1。

3 Java 代码实现

public class Solution {
    public int search(int[] nums, int target) {
        // 初始化左右指针
        int l = 0;
        int r = nums.length - 1;  // 注意这里减1，因为r是数组最后一个元素的索引

        // 当左指针小于等于右指针时，继续查找
        while (l <= r) {
            // 计算中间位置
            int mid = l + (r - l) / 2;

            // 比较中间位置的值与目标值
            if (nums[mid] > target) {
                // 目标值在左侧，更新右指针
                r = mid - 1;
            } else if (nums[mid] < target) {
                // 目标值在右侧，更新左指针
                l = mid + 1;
            } else {
                // 找到目标值，返回索引
                return mid;
            }
        }

        // 未找到目标值，返回-1
        return -1;
    }
}

4 注意事项

• 确保在计算中间位置时使用 l + (r - l) / 2 而不是 (l + r) / 2 来避免整数溢出问题。
• 初始设置 r 为 nums.length - 1，这是因为索引从 0 开始，最后一个元素的索引是 length - 1。
• 循环条件是 l <= r 而不是 l < r，这是因为我们需要包含 l == r 的情况，这可能是目标值所在的单个元素。