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.
Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0
我比較笨的就從頭到尾依次的比較，發現這并不是一個很好的辦法，雖然可以完成要求，但是所花費的時間很多。 看到好的方法是用二分查找來解決這個問題。
class Solution(object): def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ if target < nums[0]: return 0 elif target > nums[-1]: return len(nums) l, r = 0, len(nums) - 1 while l <= r: m = (l + r)/2 if nums[m] == target: return m elif nums[m] > target: if nums[m-1] < target: return m else: r = m -1 elif nums[m] < target: if nums[m+1] > target: return m+1 else: l = m + 1新聞熱點
疑難解答
