704. 二分查找 Easy

给定一个 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

解题思路

输入： 一个递增的有序数组 nums，一个目标值 target

输出： 返回目标值在数组中的下标，若不存在则返回 -1

本题属于基础查找类问题，适用于使用二分查找在有序数组中快速定位目标值。

我们通过二分查找不断缩小查找区间，具体步骤如下：

初始化左右边界：left = 0, right = len(nums) - 1

循环执行以下逻辑，直到 left > right：

计算中间位置 mid = (left + right) // 2

• 若 nums[mid] == target，说明找到目标，直接返回 mid
• 若 nums[mid] < target，说明目标值在右半部分，更新 left = mid + 1
• 若 nums[mid] > target，说明目标值在左半部分，更新 right = mid - 1

若循环结束仍未找到目标值，说明不存在，返回 -1

代码实现

python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 初始化左右指针，分别指向数组开头和结尾
        left, right = 0, len(nums) - 1

        # 当搜索区间不为空时继续循环
        while left <= right:
            # 计算中间位置，防止整型溢出
            mid = left + (right - left) // 2

            if nums[mid] == target:
                # 找到目标值，直接返回下标
                return mid
            elif nums[mid] < target:
                # 中间值比目标值小，说明目标在右半部分
                left = mid + 1
            else:
                # 中间值比目标值大，说明目标在左半部分
                right = mid - 1

        # 如果循环结束还没找到，返回 -1 表示不存在
        return -1

javascript

const search = function(nums, target) {
    // 初始化左右指针，分别指向数组的开头和结尾
    let left = 0;
    let right = nums.length - 1;

    // 当左指针小于等于右指针时，继续搜索
    while (left <= right) {
        // 计算中间位置，防止溢出写法
        const mid = Math.floor(left + (right - left) / 2);

        if (nums[mid] == target) {
            // 找到了目标值，直接返回下标
            return mid;
        } else if (nums[mid] < target) {
            // 中间值小于目标，说明目标在右边，左指针右移
            left = mid + 1;
        } else {
            // 中间值大于目标，说明目标在左边，右指针左移
            right = mid - 1;
        }
    }

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

复杂度分析

时间复杂度：O(log n)

空间复杂度：O(1)

链接

704 国际版

704 中文版