Search Insert Position

Problem Statement

Given a sorted array nums and a target value target, return the index if the target is found. If not, return the index where it would be inserted in order to maintain sorted order.

Example: nums = [1,3,5,6], target = 5 → Output: 2

Example: nums = [1,3,5,6], target = 2 → Output: 1

Approach 1: Iterative Binary Search

Explanation: Use binary search to find target or insertion point.

Time Complexity: O(log n)

Space Complexity: O(1)

low = 0
high = n - 1
while low <= high:
    mid = (low + high) // 2
    if nums[mid] == target:
        return mid
    else if nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
return low  // insertion index

Approach 2: Recursive Binary Search

Explanation: Recursively search for target; if not found, return insertion index.

Time Complexity: O(log n)

Space Complexity: O(log n) (recursion stack)

function searchInsert(nums, low, high, target):
    if low > high:
        return low
    mid = (low + high) // 2
    if nums[mid] == target:
        return mid
    else if nums[mid] < target:
        return searchInsert(nums, mid+1, high, target)
    else:
        return searchInsert(nums, low, mid-1, target)

Approach 3: Linear Scan (Naive)

Explanation: Traverse array until finding first element >= target.

Time Complexity: O(n)

Space Complexity: O(1)

for i in 0..n-1:
    if nums[i] >= target:
        return i
return n  // insert at end if all smaller