# leetcode 35. Search Insert Position（python）

2022-01-29 16:11:47

### describe

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

``````Input: nums = [1,3,5,6], target = 0
Output: 0
Copy code ``````

Example 5:

``````Input: nums = [1], target = 0
Output: 0
Copy code ``````

Note:

``````1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
-10^4 <= target <= 10^4
Copy code ``````

### analysis

According to the meaning , Gives an ordered list of integers nums And an integer target , If target stay nums in , Then directly return the index of the location , If target be not in nums in , An index guarantee is returned target Insert nums After that, it is still orderly . The idea is simple ：

• If target stay nums in , Go straight back to nums.index(target)
• Otherwise traverse nums Every element in num , If num Greater than target Directly return the index of the current location
• After traversal, if the appropriate index position is still not found , explain target Greater than nums All elements in , Go straight back to nums It's just as long as you want

The time complexity of our algorithm is required to be O(log n) , Obviously, the meaning of the question can be satisfied by directly using dichotomy , But I just don't have to , Ah, just play ～

``````class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if target in nums:
return nums.index(target)
for i, num in enumerate(nums):
if num > target:
return i
return len(nums)

Copy code ``````

### Running results

``````Runtime: 28 ms, faster than 96.37% of Python online submissions for Search Insert Position.
Memory Usage: 14.2 MB, less than 25.57% of Python online submissions for Search Insert Position.
Copy code ``````

### analysis

I lied to you , I'm sure I'll use the binary search method . Slightly ～

``````class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l, r = 0, len(nums)-1
while l <= r:
mid = (l + r)//2
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return l

Copy code ``````

### Running results

``````Runtime: 38 ms, faster than 43.70% of Python online submissions for Search Insert Position.
Memory Usage: 14 MB, less than 97.13% of Python online submissions for Search Insert Position.
Copy code ``````