二分查找-II

二分查找-II_牛客题霸_牛客网

问题简述

请实现有重复数字的升序数组的二分查找
给定一个 元素有序的（升序）长度为n的整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

思路

• Python 内置的 bisect_left 方法；

• 区别仅在于 target 不存在时的返回不同；

• 注意空数组的处理；

Python

class Solution:
    def search(self , nums: List[int], target: int) -> int:
            if not nums: return -1
            
            l, r = 0, len(nums)  # [l, r) 半开区间
            while l < r:
                m = (l + r) // 2
                if nums[m] < target:
                    l = m + 1
                else:
                    r = m
            
            return l if nums[l] == target else -1