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

题目描述

给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。

样例

Input: [5,7,7,8,8,10], 8
Output: [3,4]

Input: [5,7,7,8,8,10], 4
Output: [-1,-1]

题解

利用 左闭右开 写法

由于一个是找靠左值，一个是靠右值，写法上需要注意。

Python示例

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearchLeft(nums):
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) >> 1 
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid 
            return  left if nums[left] == target else -1 # 需要特殊判断
        # 写法一：修改逻辑，这里的 mid 一定是靠右取的
        def binarySearchRight(nums):
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right + 1) >> 1 # 注意，为了避免死循环，一定要是靠右走
                if nums[mid] > target:
                    right = mid - 1 
                else:
                    left = mid 
            return  left if nums[left] == target else -1 # 需要特殊判断
        
        # 写法二：这里实际上寻找的是比 target 大的值
        def binarySearchRight(nums):
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) >> 1
                if nums[mid] > target:
                    right = mid 
                else:
                    left = mid + 1
            return  left - 1 if nums[left - 1] == target else -1 # 这里判断的是left - 1
          
        if not nums: return [-1, -1]
        lower_bound = binarySearchLeft(nums)
        upper_bound = binarySearchRight(nums)
        return [lower_bound, upper_bound]