forked from gavinfish/leetcode-share
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path035 Search Insert Position.py
More file actions
39 lines (34 loc) · 1.16 KB
/
035 Search Insert Position.py
File metadata and controls
39 lines (34 loc) · 1.16 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
'''
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
'''
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
length = len(nums)
start = 0
end = length
while start < end:
mid = (start + end) // 2
if nums[mid] == target or (nums[mid] > target and (mid == 0 or nums[mid - 1] < target)):
return mid
if mid == length - 1 and nums[mid] < target:
return mid + 1
if nums[mid] < target:
start = mid + 1
else:
end = mid
if __name__ == "__main__":
assert Solution().searchInsert([1, 3, 5, 6], 5) == 2
assert Solution().searchInsert([1, 3, 5, 6], 2) == 1
assert Solution().searchInsert([1, 3, 5, 6], 7) == 4
assert Solution().searchInsert([1, 3, 5, 6], 0) == 0