leetcode 二分查找 35. Search Insert Position

先看题目：

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

标题不是二分， 是查找然后插入，然后看看要求：

1. array 已经被排序了
2. 要求O(log n)
3. 数组是递增的！

O(log n) 即查找/搜索空间一直在对半缩小， 所以很自然就想到了二分查找。

二分查找让我一直很晕的， 就是边界的限定。

先看代码，

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        L, R = 0, len(nums)-1


        while L <= R:
            mid = (L+R) >> 1
            print("L,Mid, R", L, mid, R)
            if nums[mid] == target:
                return mid
            else:

                if nums[mid] < target:
                    L = mid+1
                if nums[mid] > target:
                    R = mid-1
            
                
            print("L,Mid, R after", L, mid, R)

        print('output is from here ')
        return L

二分查找， 就是不停查询当前的中间值， 然后把下次搜索空间确定到左半侧或有半侧。

我们需要从目标数组nums完整开始， 所以起始搜索空间左（L）到右 （R）为 0 到 len(nums) -1， 也就是数组的索引。

举例 【1，3，5，6】， target = 4

确定索引，L = 0, R = 4-1 = 3, mid = 3//2 =1，

比较数值， numsmid = nums1 = 3

先比 numsmid != target所以失去了直接找到的机会

numsmid 3< target 4

更新坐标， 下次搜索空间必然在当前Mid的右侧，

L = mid+1 = 2

开始下一轮：

索引： L= 2， R = 3， mid = (2+3) //2 = 2

numsmid 5 != target 4 没法直接终结

numsmid > 4 说明该到左边了

R = mid -1 = 2 -1 =1

然后看下一轮：

L 2> R 1了， 搜索停止了

确定没找到， 该决定插入位置了， 是L, mid, 还是R，

插入L是对， 分类看一下

1）要插入的值在最左侧，target = 0

numsmid一直> target， 所以L不更新的， R要靠过来， 最后应该是

('L,Mid, R', 0, 1, 3)

('L,Mid, R after', 0, 1, 0)

('L,Mid, R', 0, 0, 0)

('L,Mid, R after', 0, 0, -1)

输出L

2）在最右侧，target = 7

numsmid 一直 < 7, L不停望右靠

('L,Mid, R', 0, 1, 3)

('L,Mid, R after', 2, 1, 3)

('L,Mid, R', 2, 2, 3)

('L,Mid, R after', 3, 2, 3)

('L,Mid, R', 3, 3, 3)

('L,Mid, R after', 4, 3, 3)

最后输出L，

3）在中间找到了， target = 5

('L,Mid, R', 0, 1, 3)

('L,Mid, R after', 2, 1, 3)

('L,Mid, R', 2, 2, 3)

nums2 = 5, 不用考虑后面

4） 在中间没找到， target = 4,

('L,Mid, R', 0, 1, 3)

('L,Mid, R after', 2, 1, 3)

('L,Mid, R', 2, 2, 3)

('L,Mid, R after', 2, 2, 1)

target 4在nums1 nums 2之间

在更新到L = 2时候， numsmid = nums2 = 5，

5>4, 所以R到1，其实有一个限定条件， 就是数组是递增的， 那么要插入的数字一定是>= L的，所以输出L来确定位置。

有个挺好的总结在这里， https://www.cnblogs.com/luoxn28/p/5767571.html

这个二分看似简单，边界真是让人头晕， 这次看似理解了，下次遇到类似的题再检验下。