35. 搜索插入位置

https://leetcode-cn.com/problems/search-insert-position/

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

你可以假设数组中无重复元素。

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

通过次数176,103 | 提交次数384,919

First Try

2020-07-02

最重要的是最后返回的位置与left和right之间的关系，经过推理发现当不存在的时候，返回的都是left，至少这是一个分析清晰的版本。

其实比较一下左右的情况，就会发现只有left是target的位置。终止的那一步是left = right + 1, 不过考虑的主要是终止的前一步，left = right = mid:

如果target < nums[mid], 则下一步right = mid - 1; 此后nums[right] < target < nums[mid] = nums[left]，因此target的编号为right + 1 = left。（要么right = mid - 1< 0了，但left = 0依然是正确的结果）
如果target > nums[mid], 则下一步left = mid + 1; 此后nums[left] > target > nums[mid] = nums[right],因此 target的编号为right + 1 = left (要么left = mid + 1 > len(nums) - 1了，但left= len(nums)依然是正确的结果）

从另一个角度来考虑这个问题。最后的终止条件是left = right + 1；要么是left小于target因此跳了一步加1越界，越界后left肯定大于target,因此返回left；要么是right大于target因此跳了一步减1越界，跳完后right肯定小于target，因此也是返回right + 1 = left.前面的分析（left肯定大于target或是right肯定小于target）在target小于整个数组或是大于整个数组的时候又不成立了，但再细分考虑仍然是返回left。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
  
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        # 其实比较一下左右的情况，就会发现只有left是target的位置
        # 在终止的前一步，left = right = mid 
        # 1. 如果target < nums[mid], 则right = mid - 1; 此后nums[right] < target < nums[mid] = nums[left]，因此target的编号为right + 1 = left
        # 2. 如果target > nums[mid], 则left = mid + 1; 此后nums[left] > target > nums[mid] = nums[right],因此 target的编号为right + 1 = left 
        return left

执行用时：20 ms, 在所有 Python 提交中击败了71.78%的用户
内存消耗：12.9 MB, 在所有 Python 提交中击败了7.14%的用户

bug version

虽然结果是正确的，但是在推导返回的位置与left和right的关系的时候非常混乱，其实是错误的。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target < nums[0]:
            return 0
        if target > nums[-1]:
            return len(nums)

        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        # 最后的终结情况是 left = right + 1
        # 当时在终结之前有left == right == mid
        # 1. 如果target < nums[mid]，则有right = mid - 1 = left - 1, 此时反而是target > nums[right], target需要放置的位置应该就是此时的left的位置，或者是right + 1
        # 2. 如果target > nums[mid], 则有left = mid + 1 = right + 1, 此时反而是target < nums[left], target需要放置的位置是此时right的位置，或者是left - 1
        # 前面的描述太复杂了，或者可以认为最终left = right + 1,也就是nums[left] > nums[right]
        # 靠，感觉还是有点绕，没法快速想出来，不好办啊
        # print(target, left, right, nums)
        if target > nums[right]:
            return left
        if target < nums[left]:
            return right

执行用时：24 ms, 在所有 Python 提交中击败了48.84%的用户
内存消耗：13.2 MB, 在所有 Python 提交中击败了7.14%

35. 搜索插入位置​

First Try​

35. 搜索插入位置

First Try