LeetCode | Search Insert Position | Microsoft Interview Questions | Geek Hacker
Problem Statement
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.
Constraints
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
contains distinct values sorted in ascending order.-104 <= target <= 104
Examples
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
Example 4
Input: nums = [1,3,5,6], target = 0
Output: 0
Example 5
Input: nums = [1], target = 0
Output: 0
Analysis
In order to find the index of a target in a sorted array using an algorithm with O(log n)
runtime complexity, binary search will be used because it has O(log n)
time complexity.
If the value at some index is less than the target, then there is no need to check elements which are left to that index, as they would be even smaller. So, we can use a Binary Search to find the Search Insert Position.
Algorithm
- Create a binarySearch() function that returns the required index
- Set lower and upper bounds as
0
andn-1
respectively, such thatn
= size of the array - While
start <= end
- Find the middle index of these limits as
mid = (start + end) // 2
- If
nums[mid] == target
, returnmid
- In case the value is smaller, we move to the right half using
start = mid + 1
- In case the value is greater, we move to the left half using
right = mid — 1
- Return the insert position
end + 1
Python 3 Code
def searchInsert(self, nums, target):
# Lower and upper bounds
start = 0
end = len(nums) - 1
# Traverse the search space
while start <= end:
mid =(start + end)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
start = mid + 1
else:
end = mid-1
# Return the insert position
return end + 1
Complexity
Time Complexity
O(log n)
Space Complexity
O(1)
For more LeetCode problems’ solutions, visit my GitHub repo.
If you enjoyed reading this article, please recommend and share it to help others find it!