34. Find First and Last Position of Element in Sorted Array

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

solution

• 由于mid可能落在中间target地带. 递增的序列等于即意味着找到并返回

• lower bound，即使等于，右边界也继续压缩

• upper bound，即使等于，左边界也继续压缩

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

        l = self.low_bound(nums, target)
        r = self.high_bound(nums, target)

        if l >= len(nums) or nums[l] != target:  # 也可以通过 l > r
            return [-1, -1]  
        return [l, r-1]
    
    def low_bound(self, nums, target):
        l = 0
        r = len(nums) - 1  # 左闭右闭
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] < target:  # 求上下边界时, 等于没有返回。也导致后续输出后判断是否根本没找到
                l = mid + 1
            elif nums[mid] >= target:
                r = mid - 1
        return l  # 注意l

    def high_bound(self, nums, target):
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] <= target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1       
        return l  # 注意l, 最后输出upper bound - 1

时间复杂度：O(log(n)) 空间复杂度：O(1)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]
        
        l = self.get_lower(nums, target)
        r = self.get_higher(nums, target)
        if l < len(nums) and l < r:
            return [l, r-1]
        return [-1, -1]
    
    def get_lower(self, nums, target):
        l = 0
        r = len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        return l
    
    def get_higher(self, nums, target):
        l = 0
        r = len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid
        return l

follow up

Count of Unique elements in a very large sorted Array