塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-35搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素

最初想法:
从头遍历,如果存在,返回索引。
如果不存在,插入适当位置,剩余元素往后挪。

改进下使用二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def searchInsert( 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
else:
high = mid - 1
# 现在mid处元素应该是最接近target
if nums[mid] > target:
return mid
else:
return mid + 1
if help:小手一抖点个广告 or 大手一挥资助一下