在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

问题简述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
要求：时间复杂度 O(logN)

思路：二分查找

• 参考 from bisect import bisect_left, bisect_right

• 代码细节见注释；

Python 写法 1：左闭右开区间

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums: return [-1, -1]

        # 找最左侧的 target
        l, r = 0, len(nums)
        while l < r:  # 退出循环时 l == r
            m = l + (r - l) // 2
            if nums[m] < target:
                l = m + 1
            else:
                r = m

        # 不存在 target
        if l == len(nums) or nums[l] != target:
            return [-1, -1]
        
        L = l
        # 找最右侧的 target
        l, r = 0, len(nums)
        while l < r:
            m = l + (r - l) // 2
            if nums[m] <= target:  # 与找最左侧只有 <= 这一处区别
                l = m + 1
            else:
                r = m
        
        R = r - 1  # 注意 r 是开区间
        return [L, R]

Python 写法 2：利用 Python 特性减少代码量

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums: return [-1, -1]

        def bisect(l, r, com):
            while l < r:
                m = l + (r - l) // 2
                if eval(f'{nums[m]} {com} {target}'):
                    l = m + 1
                else:
                    r = m
            return l  # 退出循环时 l == r

        # 找最左侧的 target
        L = bisect(0, len(nums), '<')
        # 不存在 target
        if L == len(nums) or nums[L] != target:
            return [-1, -1]
        
        R = bisect(0, len(nums), '<=') - 1
        return [L, R]