Crack the Backend

Problem Statement

Given a sorted array of distinct integers nums and a target value, return the index where target would be inserted to keep the array sorted. If target is already in nums, return its index. There are no duplicates.

We need the lower bound of target: the first index i such that nums[i] >= target. That is exactly the insert position. If target is larger than all elements, return nums.length.

Key Observations

This is the standard lower_bound (or leftmost position for target): the smallest index i such that nums[i] >= target. Use binary search with range [0, nums.length] (so we can return n if target is greater than all). If nums[mid] < target, we need to search the right half (left = mid + 1). Otherwise nums[mid] >= target, so mid is a candidate and we search the left half (right = mid). When left == right, we have the answer.
Loop condition left < right and right = mid (not mid - 1) so we don't skip the candidate.

Approach

High-level: Binary search for the first index i where nums[i] >= target. Search space [0, nums.length]. If nums[mid] < target, left = mid + 1; else right = mid. Return left.

Steps:

left = 0, right = nums.length. While left < right: mid = left + (right - left) / 2. If nums[mid] < target, left = mid + 1; else right = mid.
Return left.

Implementation

Java

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }

    return left;
}

Test Cases

Example 1

Input

nums = [1,3,5,6], target = 5

Expected

2

Explanation

5 found at 2.

Complexity Analysis

Time: O(log n).
Space: O(1).

Follow-ups

Upper bound: first index where nums[i] > target.