Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume NO duplicates in the array.

Example

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

Solution

note: 做比较的时候尽量把target放到右边比较. 如果三段关系需要使用if elif else, 变形题目, 插入位置也决定了

class Solution:
    """
    @param A : a list of integers
    @param target : an integer to be inserted
    @return : an integer
    """
    def searchInsert(self, nums, target):
        if len(nums) == 0:
            return 0

        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end-start) / 2
            if nums[mid] < target:
                start = mid
            else:
                end = mid
        if nums[start] >= target:
            return start
        elif nums[end] >= target:
            return end
        else:
            return end + 1