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

1. Create a binarySearch() function that returns the required index
2. Set lower and upper bounds as 0 and n-1 respectively, such that n = size of the array
3. While start <= end
4. Find the middle index of these limits as mid = (start + end) // 2
5. If nums[mid] == target, return mid
6. In case the value is smaller, we move to the right half using start = mid + 1
7. In case the value is greater, we move to the left half using right = mid — 1
8. 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!