題目
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小的數(shù)馍刮，這樣時(shí)間復(fù)雜度是O(n)。更好的方法是二分搜索窃蹋，將時(shí)間復(fù)雜度降為O(logn)卡啰。因?yàn)樽詈笠祷叵聵?biāo)，所以用low和high兩個(gè)變量?jī)?chǔ)存二分搜索的上下限警没；用遞歸的話不能返回原數(shù)組的下標(biāo)匈辱。二分搜索的時(shí)候要小心陷入死循環(huán)
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保證下限在增大，防止死循環(huán)
else:
high = mid - 1 # -1保證上限在減小杀迹，防止死循環(huán)
return low
