# [leetcode question brushing Python] 35. Search the insertion position

2022-07-24 22:06:02

# 1 subject

Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .
Please use a time complexity of O(log n) The algorithm of .

Example 1:

Input : nums = [1,3,5,6], target = 5
Output : 2

Example 2:

Input : nums = [1,3,5,6], target = 2
Output : 1

Example 3:

Input : nums = [1,3,5,6], target = 7
Output : 4

# 2 analysis

Insert with binary search , Pay attention to boundary judgment , Insertion position , If you insert target Than a Big , Then insert in a Behind . At this time, take an example to draw , You can understand .
such as nums = [1,3,5,6], target=4 and target=2

# 3 Python Realization

``````def searchInsert(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)-1
result = len(nums)
while l <= r:
mid = int((l+r)/2)
if target<=nums[mid]:
r = mid-1
result = mid
else:
l = mid+1
return result
``````