algoadvance

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

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

Clarifying Questions

  1. Can the input array be empty?
    • No, the problem guarantee that the array will not be empty.
  2. Are there any constraints on the input size?
    • No, but efficient O(log n) solution is expected which hints towards using binary search.

Strategy

To achieve the O(log n) runtime complexity, we can use a binary search approach. Here’s the strategy in detail:

  1. Initialize Pointers:
    • Set two pointers, left at the beginning (0) and right at the end (len(nums) - 1) of the array.
  2. Binary Search Loop:
    • Compute the middle index.
    • If nums[middle] is equal to the target, return middle.
    • If nums[middle] is less than the target, move the left pointer to middle + 1 to search in the right subarray.
    • If nums[middle] is greater than the target, move the right pointer to middle - 1 to search in the left subarray.
  3. End Condition:
    • If the loop ends without finding the target, the left pointer will indicate the correct insertion position.

Code

def search_insert(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return left

Time Complexity

This approach ensures efficient and correct insertion/index location of the target in the sorted array.

Try our interview co-pilot at AlgoAdvance.com