[LeetCode] Search Insert Positio

题目

原题地址

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

思路

最naive的方法就是遍历，找到所有比target小的数，这样时间复杂度是O(n)。更好的方法是二分搜索，将时间复杂度降为O(logn)。因为最后要返回下标，所以用low和high两个变量储存二分搜索的上下限；用递归的话不能返回原数组的下标。二分搜索的时候要小心陷入死循环

python代码

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low = 0
        high = len(nums) - 1
        while(low <= high):
            mid = (low + high) / 2
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                low = mid + 1 # +1保证下限在增大，防止死循环
            else:
                high = mid - 1 # -1保证上限在减小，防止死循环
        return low