一、题目
力扣地址：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))
三、其他解法与类似
...