0704. 二分查找

0704. 二分查找 #

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

题目大意 #

给定一个升序的数组 nums,和一个目标值 target,返回 target 在数组中的位置,如果找不到,则返回 -1。

解题思路 #

纯粹考察二分查找。

算法基本原理:

设定左右节点为数组两端。不断判断两个节点中心位置与目标值的大小。

  • 如果中心位置与目标值相等,则返回中心位置。
  • 如果中心位置小于目标值,则将左节点设置为中心位置+1,然后继续在右侧搜索。
  • 如果中心位置大于目标值,则将右节点设置为中心位置-1,然后继续在左侧搜索。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        ans = -1
        while left <= right:
            mid = (left+right)//2
            if nums[mid] == target:
                ans = mid
                left = mid+1
                return ans
            if nums[mid] < target:
                left = mid+1
            else:
                right = mid-1
        return ans
本站总访问量  次  |  您是本站第  位访问者