Day 35 ：寻找有序数组元素插入位置

Day 35 ：寻找有序数组元素插入位置

大家注意观察，上面的示例 1:

输入: [1,3,5,6], 待插入元素为 5 输出: 2

这意味着如果出现重复元素，则靠前插入。

如果插入 5，输出 3 ，靠后插入。

class Solution(object):
    def searchInsert(self, nums, target):
        left, right = 0, len(nums) -1
        if target < nums[0] :return 0
        if target >= nums[-1]: return len(nums)
        while left <=right:
            mid = (left + right )//2
            if target == nums[mid]:
                while nums[mid+1] == nums[mid]:
                    mid +=1
                return mid+1
            elif target > nums[mid]:
                left = mid +1
            else:
                right = mid -1
        return mid+1


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

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))