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
自己写的~~
1 class Solution(object): 2 def searchInsert(self, nums, target): 3 """ 4 :type nums: List[int] 5 :type target: int 6 :rtype: int 7 """ 8 if target < nums[0]: 9 return 0 10 for i in nums: 11 if i >= target: 12 return nums.index(i) 13 return len(nums)
注意讨论边界情况啊！
1 class Solution(object): 2 def searchInsert(self, nums, target): 3 """ 4 :type nums: List[int] 5 :type target: int 6 :rtype: int 7 """ 8 return len([x for x in nums if x<target])
[x for x in nums if x<target]生成一个比target小的列表
1 class Solution(object): 2 def searchInsert(self, nums, target): 3 """ 4 :type nums: List[int] 5 :type target: int 6 :rtype: int 7 """ 8 ans = 0 9 low,high,mid = 0,len(nums)-1,0 10 while(low <= high): 11 mid = (low + high)/2 12 if nums[mid] > target: 13 high = mid - 1 14 elif nums[mid] < target: 15 low = mid + 1 16 else: 17 return mid 18 if high < mid: 19 return mid 20 elif low > mid: 21 return low
二分法~
原文：http://www.cnblogs.com/fullest-life/p/6541682.html