题目描述

给定一个升序的数组和目标值，如果数组中含有目标值，则返回位置；否则返回插入的位置使得插入后仍满足升序。
假设数组中没有重复元素。

样例

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

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

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

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

更新
l,r, mid=(l+r)/2,下取得整数， r=m, l=m+1, return r
l,r, mid=(l+r+1)/2,上取得整数， l=m, r=m-1, return l

(mid+1，r] 模板1 更新
[l,mid], 模板2 更新
所以 求平方根整数，选择 mid=(l+r+1)/2,上取得整数， l=m, r=m-1,

模板2
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if (len(nums)==0):
            return 0
        l=0 
        r=len(nums)-1  #目标索引在左边<=mid,更新方式是 r=m-1,l=m ,mid=(l+r +1)/2

        while (l<r):
            mid = (l+r +1)/2
            if nums[mid]>target:
                r=mid-1  #r 不包括边界
            else:
                l=mid
        if target>nums[r]:
            return r+1
        return r
a=Solution()
a.searchInsert([1,2,5,6],4)


模板1
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if (len(nums)==0):
            return 0
        l=0 
        r=len(nums)-1  #目标索引在左边<=mid,更新方式是 r=m-1,l=m ,mid=(l+r +1)/2
        while (l<r):
            mid = (l+r)/2
            if nums[mid]>=target:
                r=mid
            else:
                l=mid+1
        if nums[r]<target:
            return len(nums)
        return l
a=Solution()
a.searchInsert([1,2,5,6],7)