LeetCode小白菜笔记[11]：Search Insert Position

35. Search Insert Position [Easy]

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:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 1:

Input: [1,3,5,6], 0
Output: 0

相当于升级版的二分查找，加入了找不到的返回值。代码如下：

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l = 0
        r = len(nums) - 1
        if target <= nums[0]:
            return 0
        elif target > nums[-1]:
            return len(nums)
        else:
            while l <= r :
                m = (l + r) // 2
                if target < nums[m] :
                    r = m
                elif target > nums[m] :
                    l = m
                else :
                    return m
                if l+1 == r and not target == m :
                    return r

二分查找有通用的方法，关键是对于边界情况要考虑一下。然后就是如果能保证一定target在list中的话，那么最后一个if是为了避免最终切出来的两个元素的区间的middle是左边或者右边而导致的死循环，如【1, 2】中要找到1，如果middle向下取整则m = 0，所以 target=nums[m]，但是要找到2的话，m = 0，target大于中间的值，所以 l = m，会一直这样。如果已知一定能找到，则当元素为2的时候直接返回右边的值（对于求m时向下取整）。对于查不到的，返回 r 也是需要插入的位置。这是最后一个 if 的作用。

discuss 里面的一个高级玩家：

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """       
        return len([x for x in nums if x<target])

不过速度是不是慢了点。。。

总结：

好久没刷了。。。进度堪忧，近期要加快速度。。。

2018.1.20 18:22

如果不是竭力对抗严冬，就不能体会春天的温暖。
—— 星野道夫