35. Search Insert Position - Detailed Explanation

Problem Statement

You are given a sorted array of distinct integers and a target value. Your task is to return the index if the target is found. If not, return the index where the target would be inserted to maintain the sorted order. The solution must run in O(log n) time complexity.

Examples:

1. Example 1:

   • Input: nums = [1, 3, 5, 6], target = 5
   • Output: 2
   • Explanation: The target 5 is found at index 2.

2. Example 2:

   • Input: nums = [1, 3, 5, 6], target = 2
   • Output: 1
   • Explanation: The target 2 is not in the list. It would be inserted at index 1 to maintain sorted order.

3. Example 3:

   • Input: nums = [1, 3, 5, 6], target = 7
   • Output: 4
   • Explanation: The target 7 is greater than all elements, so it would be inserted at the end of the list.

Constraints:

• The array is sorted in ascending order.
• All elements are distinct.
• The solution should achieve O(log n) time complexity.

Hints Before Solving

• Hint 1: Since the array is sorted, binary search is an ideal strategy.
• Hint 2: When the target is not found, pay attention to the final state of the low pointer; it indicates the correct insertion position.
• Hint 3: Consider edge cases where the target is less than the first element or greater than the last element.

Approaches to Solve the Problem

Approach 1: Brute Force Linear Scan (Not Optimal)

Explanation:

• Idea: Iterate through the array and find the first element that is greater than or equal to the target.
• Process:
  1. Loop through the array.
  2. If an element is equal to or greater than the target, return its index.
  3. If the loop completes without finding such an element, return the length of the array.

Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Note: Although simple, this approach does not meet the O(log n) time requirement.

Approach 2: Optimal Binary Search

Explanation:

• Idea: Use binary search to efficiently determine the target's index or the correct insertion point.
• Process:
  1. Initialize two pointers: low = 0 and high = len(nums) - 1.
  2. While low <= high:
     • Compute mid = (low + high) // 2.
     • If nums[mid] equals the target, return mid.
     • If nums[mid] is less than the target, update low = mid + 1.
     • If nums[mid] is greater than the target, update high = mid - 1.
  3. When the loop ends, low will be the insertion position for the target.

Visual Walkthrough:

Consider nums = [1, 3, 5, 6] and target = 2:

• Step 1: low = 0, high = 3
  • mid = (0 + 3) // 2 = 1, and nums[1] = 3 which is greater than 2.
  • Update high = mid - 1 = 0.
• Step 2: Now, low = 0 and high = 0
  • mid = (0 + 0) // 2 = 0, and nums[0] = 1 which is less than 2.
  • Update low = mid + 1 = 1.
• End: Loop terminates with low = 1, which is the correct insertion index.

Complexity:

• Time Complexity: O(log n)
• Space Complexity: O(1)

Code Implementations

Python Implementation