We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Search Insert Position

Number: 35

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Bloomberg, Meta, Accenture, Amazon, Apple, Adobe, Uber, Yahoo, Zoho

Problem Description

Given a sorted array of distinct integers and a target value, determine the index at which the target is located, or if it is not present, the index where it should be inserted to maintain the sorted order.

Key Insights

  • The array is sorted, enabling the use of binary search.
  • Binary search achieves a time complexity of O(log n) which meets the problem constraints.
  • When the target is not found during the search, the final low pointer represents the correct insertion index.

Space and Time Complexity

Time Complexity: O(log n) due to binary search.
Space Complexity: O(1) as no extra space is used.

Solution

We use binary search to find the target in the sorted array. Initialize two pointers, low and high. At each iteration, compute the mid index. If the value at mid matches the target, return mid. If the target is less than the mid value, adjust the high pointer; if greater, adjust the low pointer. When the iterations finish without finding the target, return the low pointer, which represents the correct insertion index.

Code Solutions

# Python solution using binary search
def searchInsert(nums, target):
    # Initialize low and high pointers for binary search
    low, high = 0, len(nums) - 1
    # Perform binary search until low pointer exceeds high pointer
    while low <= high:
        mid = (low + high) // 2  # Calculate the middle index
        if nums[mid] == target:  
            return mid  # Return mid if target is found
        elif target < nums[mid]:
            high = mid - 1  # Narrow search on the left side
        else:
            low = mid + 1  # Narrow search on the right side
    # Return low pointer as the insertion index when target is not found
    return low

# Example usage
print(searchInsert([1, 3, 5, 6], 5))  # Output: 2
← Back to All Questions