No.35 搜索插入位置

题目：给定一个排序数组和一个目标值，在数组中找到目标值。并返回其索引。如果目标值不在数组中，返回它将被顺序插入的位置。
例：

输入: [1,3,5,6], 5
输出: 2

输入: [1,3,5,6], 2
输出: 1

输入: [1,3,5,6], 7
输出: 4

输入: [1,3,5,6], 0
输出: 0

题解：
一、二分查找

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        size = len(nums)
        if size == 0:
            return 0

        # 特判
        if nums[size - 1] < target:
            return size

        left = 0
        right = size - 1

        while left < right:
            # left + right 在 Python 中如果发生整型溢出，Python 会自动转成长整形
            mid = (left + right) // 2
            # 严格小于 target 的元素一定不是解
            if nums[mid] < target:
                # 下一轮搜索区间是 [mid + 1, right]
                left = mid + 1
            else:
                # 下一轮搜索区间是 [left, mid]
                right = mid
        return left

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

知识点：
二分查找-双指针
二分查找是一个逐次缩小查找空间的过程。
初始化：左指针（left）在最左端，右指针（right）在最右端。
第一次比较：mid=（left+right）//2 （向上取整）
若target>nums[mid]，则下一次查找空间为右半段，做法是将左指针移动至mid+1；反之类似，将右指针移动至mid-1。
每次比较都对子查找空间进行这样的分割，直到target==nums[mid]表示找到了；left>right或right这种思想每次都将查找空间减半，因此复杂度为。