35. Search Insert Position

Intuition

Since the array is sorted, we can leverage binary search to find the target efficiently in O(log n) time.

• If the target exists in the array, binary search will locate and return the index.

• If not found, the correct insert position for the target is exactly where the left pointer ends up — this is where the value would maintain the sorted order.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{n})$

Code

public int searchInsert(int[] nums, int target) {
    // Initialize binary search boundaries
    int left = 0, right = nums.length - 1;
    
    // Perform binary search
    while (left <= right) {
        int mid = (left + right) >> 1; // Same as (left + right) / 2

        // If target found at mid, return index
        if (nums[mid] == target) return mid;

        // If target is greater, discard left half
        if (nums[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, discard right half
        else {
            right = mid - 1;
        }
    }

    // If not found, left is the correct insertion index
    return left;
}