0704. 二分查找

0704. 二分查找 #

  • 标签:数组、二分查找
  • 难度:简单

题目大意 #

描述:给定一个升序的数组 nums,和一个目标值 target

要求:返回 target 在数组中的位置,如果找不到,则返回 -1。

说明

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

示例

  • 示例 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 = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

解题思路 #

思路 1:二分查找 #

设定左右节点为数组两端,即 left = 0right = len(nums) - 1,代表待查找区间为 [left, right](左闭右闭)。

取两个节点中心位置 mid,先比较中心位置值 nums[mid] 与目标值 target 的大小。

  • 如果中心位置值 nums[mid] 与目标值 target 相等,则返回中心位置。
  • 如果中心位置值 nums[mid] 小于目标值 target,则将左节点设置为 mid + 1,然后继续在右区间 [mid + 1, right] 搜索。
  • 如果中心位置值 nums[mid] 大于目标值 target,则将右节点设置为 mid - 1,然后继续在左区间 [left, mid - 1] 搜索。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        # 在区间 [left, right] 内查找 target
        while left <= right:
            # 取区间中间节点
            mid = (left + right) // 2
            # 如果找到目标值,则直接返回中心位置
            if nums[mid] == target:
                return mid
            # 如果 nums[mid] 小于目标值,则在 [mid + 1, right] 中继续搜索
            elif nums[mid] < target:
                left = mid + 1
            # 如果 nums[mid] 大于目标值,则在 [left, mid - 1] 中继续搜索
            else:
                right = mid - 1
        # 未搜索到元素,返回 -1
        return -1

思路 1:复杂度分析 #

  • 时间复杂度:$O(\log_2n)$。
  • 空间复杂度:$O(1)$。
本站总访问量  次  |  您是本站第  位访问者