Easy

题目描述

给定一个按升序排列的整数数组 nums 和一个目标值 target，编写一个函数在 nums 中搜索 target。如果目标值存在返回下标，否则返回 -1。

你必须设计一个时间复杂度为 O(log n) 的算法。

示例 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 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • nums 中的所有整数互不相同
  • nums 按升序排列

解题思路

这是一道经典的二分查找题目，考查最基础的二分查找算法实现。

解题思路

二分查找算法： 在有序数组中查找目标值的最优方法。算法通过不断缩小搜索区间来定位目标值。

核心思想：

  1. 维护两个指针 left 和 right，分别指向搜索区间的左右边界
  2. 计算中间位置 mid = left + (right - left) / 2，避免溢出
  3. 比较 nums[mid] 与 target：
    • 如果相等，直接返回 mid
    • 如果 nums[mid] < target，说明目标在右半部分，更新 left = mid + 1
    • 如果 nums[mid] > target，说明目标在左半部分，更新 right = mid - 1
  4. 重复上述过程直到找到目标或搜索区间为空

边界处理： 使用左闭右闭区间 [left, right] 的写法，循环条件为 left <= right。这种写法清晰明确，容易理解和实现。

时间复杂度 O(log n) 满足题目要求，是在有序数组中查找元素的最优解法。

代码实现

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
};

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
        
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        
        if (nums[mid]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)每次比较都会将搜索区间缩小一半
空间复杂度O(1)只使用了常数个额外变量

相关题目