Domain 1EasyCORE

Search Insert Position

The problem requires finding the position of a target value in a sorted array of distinct integers. If the target is found, return its index; otherwise, return the index where it would be inserted to maintain the sorted order. The input is a sorted array `nums` and an integer `target`. The output is an integer representing the insertion index.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Binary Search

35. Search Insert Position

Model: qwen2.5-coder:14b
Topics: Array,Binary Search
FAANG asked: 1
Acceptance rate: 42.9%


Problem Breakdown

The problem requires finding the position of a target value in a sorted array of distinct integers. If the target is found, return its index; otherwise, return the index where it would be inserted to maintain the sorted order. The input is a sorted array nums and an integer target. The output is an integer representing the insertion index.

Inputs:

  • A sorted array of distinct integers (nums)
  • An integer (target)

Outputs:

  • An integer representing the index where the target should be inserted

Implicit Constraints or Edge Cases:

  • The array can be empty.
  • The target could be less than the smallest element, equal to an element in the array, or greater than the largest element.

Intuition

A brute-force approach would involve iterating through the array and checking each element until we find the correct position. This method has a time complexity of O(n), which is inefficient for large arrays.

The key insight is that since the array is sorted, we can use binary search to achieve a more efficient solution with a time complexity of O(log n). Binary search works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half.

Approach

  1. Initialize Pointers: Start with two pointers, left and right, representing the current search bounds.
  2. Binary Search Loop:
    • Calculate the middle index mid.
    • If the element at nums[mid] is equal to the target, return mid.
    • If the element at nums[mid] is less than the target, move the left pointer to mid + 1.
    • If the element at nums[mid] is greater than the target, move the right pointer to mid - 1.
  3. Insertion Point: When left exceeds right, the loop terminates, and left will be the correct insertion index.

Complexity Analysis

  • Time Complexity: O(log n) because we are using binary search.
  • Space Complexity: O(1) as we are only using a constant amount of extra space for pointers.

Solution

def searchInsert(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

Edge Cases Handled

  • Empty Array: If the array is empty, left will remain 0, which is the correct insertion index.
  • Target Less Than Minimum Element: The loop will terminate with left at 0, indicating the target should be inserted at the beginning.
  • Target Greater Than Maximum Element: The loop will terminate with left equal to the length of the array, indicating the target should be inserted at the end.
  • Single Element Array: Handles correctly by adjusting left and right pointers based on comparison.