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

一、题目

力扣地址：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

二、解法思路：

也是二分查找相关题目，详细解法看注释

from typing import List


class Solution:
    """
    leetcode:34
    二分查找类题目，与传统二分查找的区别为，需要在一个不递减的数组中找到左右边界。
    较为简单的做法是采用两个二分查找，分别找到左边界和右边界。
        寻找左边界：当二分查找到第一个target时，不return,而是把此处暂时标记为左边界，并把该index左边的数组继续进行查找，
        若还能找到target,则更新左边界，如此反复。
        寻找右边界：同左边界一样，只不是找到一个target时，把index的右边继续进行查找
    """

    def searchInsert(self, nums: List[int], target: int) -> int:
        # 特殊处理边界，直接返回
        if not nums:
            return [-1, -1]
        if target > nums[len(nums) - 1] or target < nums[0]:
            return [-1, -1]
        left = 0
        right = len(nums) - 1
        target_left_idx = -1
        target_right_idx = -1
        while left <= right:
            middle = left + ((right - left) >> 1)
            if target == nums[middle]:
                target_left_idx = middle
                right = middle - 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                left = middle + 1
        # 初始化left和right
        left = 0
        right = len(nums) - 1
        while left <= right:
            middle = left + ((right - left) >> 1)
            if target == nums[middle]:
                target_right_idx = middle
                left = middle + 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                left = middle + 1

        return [target_left_idx, target_right_idx]


if __name__ == '__main__':
    s = Solution()
    print(s.searchInsert(nums=[], target=0))

三、其他解法与类似

...