在有序数组中查找插入元素的位置，显然可以使用二分查找。这篇题解提供的思路是“排除法”，即在循环的过程中，不断排除不需要的解，最后剩下的那个元素就一定是我们想要的。

首先，插入位置有可能在数组的末尾（题目中的示例 3），需要单独判断；

其次，如果待插入元素比最后一个元素严格小，并且在这个数组中有和插入元素一样的元素，返回任意一个位置即可；

否则，插入的位置应该是严格大于 target 的第 1 个元素的位置。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: list[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)-1
        if target > nums[-1]:return right+1
        if target <= nums[0]:return left
        # import ipdb; ipdb.set_trace()  # XXX BREAKPOINT
        while left <= right:
            mid = (left + right) // 2
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                left = mid + 1
                print(f'Left: {left} Right: {right}')
            else:
                right = mid -1
                print(f'Left: {left} Right: {right}')
        return mid



def test_serarchInsert():
    s = Solution()
    assert s.searchInsert([1,3,5,6],5) == 2
    assert s.searchInsert([1,3,5,6],2) == 1

s = Solution()
print(s.searchInsert([1,3,5,6,8,10,12,15,19,20,22,24,25,26,27,28],20))
print(s.searchInsert([1,3,5,6],2))
print(s.searchInsert([1,3,5,6],1))
print(s.searchInsert([1,3,5,6],6))
print(s.searchInsert([1,3,5,6],7))
print(s.searchInsert([1,3,5,6],7))