【力扣日记】704 标准二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

算法思路

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l,r=0,len(nums)
        # 因为r是边界，所以while l<r 即可，结束条件是l==r，此时l越界或下标l的值已经比较过
        while l<r:
            mid=(l+r)//2
            if nums[mid]==target:return mid
            # nums[mid]>target表示中值大于目标值，此时r=mid，与下一行的l=mid+1
            if nums[mid]>target:r=mid
            elif nums[mid]<target:l=mid+1
        return -1

执行用时 :288 ms, 在所有 Python3 提交中击败了86.45%的用户

当l,r=0,len(nums)-1时：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l,r=0,len(nums)-1
        while l<=r:
            mid=(l+r)//2
            if nums[mid]==target:return mid
            if nums[mid]>target:r=mid-1
            elif nums[mid]<target:l=mid+1
        return -1

执行用时 :292 ms, 在所有 Python3 提交中击败了77.69%的用户