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

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

# -*- coding:utf-8 -*-
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 取起始下标
        left, right = 0, len(nums) - 1
        # 二分查找第一个（尽量缩小右侧）
        while left < right:
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid + 1
        # 没找到
        if not nums or nums[left] != target:
            return [-1, -1]
        # 二分查找最后一个（尽量缩小左侧）
        a, b = left, len(nums) - 1
        while a < b:
            mid = (a + b + 1) // 2
            if nums[mid] <= target:
                a = mid
            else:
                b = mid - 1
        return [left, a]
if __name__ == '__main__':
    nums = [2, 2]
    target = 1
    print(Solution().searchRange(nums, target))

思路：使用两次二分法，分别从左、右向target逼近（一次尽全力缩小右侧，因此第一个target应该是left，一次尽全力缩小左侧，因此第一个target是right。返回[left,right]即可），依次获得target的第一次位置和最后一次位置。