力扣-35-搜索插入位置

一、题目

力扣地址：https://leetcode.cn/problems/search-insert-position/

二、解法思路

与标准的二分查找一直，唯一的区别为，若所需target不在nums中，需要找到insert的索引

from typing import List


class Solution:
    """
    leetcode:35
    在二分法的基础上延伸，若无法找到元素，则需要确定该元素要被insert到哪个位置。
    对于二分法左闭右闭的解法来说，当left = right时，表示该target不在nums中，且此时因为二分法的不断缩小left和right,
    其实正好等于需要insert的位置
    """

    def searchInsert(self, nums: List[int], target: int) -> int:
        # 特殊处理边界，直接返回
        if target > nums[len(nums) - 1]:
            return len(nums)
        if target < nums[0]:
            return 0
        # 标准左闭右闭的二分法，最后的return改为left边界
        left = 0
        right = len(nums) - 1
        while left <= right:
            middle = left + ((right - left) >> 1)
            if nums[middle] == target:
                return middle
            elif nums[middle] > target:
                right = middle - 1
            else:
                left = middle + 1
        else:
            return left


if __name__ == '__main__':
    s = Solution()
    print(s.searchInsert(nums=[1, 3, 5, 6], target=7))

三、其他解法与类似

...