题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
例子
searchInsert([1,3,5,6], 5) -> 2
searchInsert([1,3,5,6], 2) -> 1
searchInsert([1,3,5,6], 7) -> 4
searchInsert([1,3,5,6], 0) -> 0假设
- 输入的参数均不为空
tips
- 二分查找
答案
解法1
def searchInsert(nums,target):
n = len(nums)
left = 0
right = n - 1
ans = n
while left <= right:
mid = (left + right) // 2
if target <= nums[mid]:
ans = mid
right = mid - 1
else:
left = mid + 1
return ans 性能：
- 时间复杂度
O(nlogn) - 空间复杂度
O(1)
关键点：
- 二分查找
解法2：
def searchInsert(nums, target):
i, j, m = 0, len(nums) - 1, 0
while i <= j:
m = (i + j) // 2
if target == nums[m]:
return m
elif target > nums[m]:
i = m + 1
if target > nums[j]:
return j + 1
else:
if target < nums[i]:
return i
j = m - 1
return m