-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsearch-insert-position.py
More file actions
59 lines (54 loc) · 1.75 KB
/
search-insert-position.py
File metadata and controls
59 lines (54 loc) · 1.75 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# encoding: utf-8
__author__ = 'zhangwei'
# 递归版本
class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {integer}
def searchInsert(self, nums, target):
n = len(nums)
if n == 0:
return 0
return self.aux(nums, 0, n, target)
# auxiliary method
def aux(self, nums, start, stop, target):
if stop-start <= 2: # 小于等于两个元素
# 可以拆分为stop-start == 1和stop-start == 2两种情况，逻辑会更清晰一些
if target <= nums[start]:
return start
elif target > nums[stop-1]:
return stop
else:
return stop-1
mid = (start + stop) / 2
if target == nums[mid]:
return mid
elif target < nums[mid]:
return self.aux(nums, start, mid, target)
else:
return self.aux(nums, mid+1, stop, target)
# 迭代版本
class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {integer}
def searchInsert(self, nums, target):
n = len(nums)
if n == 0:
return 0
start, stop = 0, n
while start < stop:
if stop-start <= 2: # 可以拆分为stop-start == 1和stop-start == 2两种情况，逻辑会更清晰一些
if target <= nums[start]:
return start
elif target > nums[stop-1]:
return stop
else:
return stop-1
mid = (start+stop) / 2
if target == nums[mid]:
return mid
elif target < nums[mid]:
stop = mid
else:
start = mid+1