[BinarySearch]035 Search Insert

• 分类：BinarySearch

• 考察知识点：BinarySearch

• 最优解时间复杂度：O(logn)

• 最优解空间复杂度：O(1)

35. 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:

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 4:

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

代码：

方法:

class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        start=0
        end=len(nums)-1
        while(end-start>1):
            mid=(end-start)//2+start
            if target==nums[mid]:
                return mid
            elif target>nums[mid]:
                start=mid
            else:
                end=mid
        
        if nums[start]>=target:
            return start
        elif nums[end]<target:
            return end+1
        else:
            return end

---

讨论：

1.一道简单基础的binary search的题
2.当然最后的case by case的几种情况也是需要注意的

035