Search Insert Position

Given a sorted array and a target, return the index of the target, or the index where it would be inserted to keep the array sorted.

EasyMust DoBinary SearchLower BoundLeetCode

Why solve this?

It's the first 'lower bound' variant: the answer exists even when the target isn't present, which is a different mental model than exact-match search.

Pattern recognition

"Where would this value go if inserted" in a sorted array is a lower-bound binary search — the loop keeps narrowing even after 'not found' would normally exit.

Prerequisites

Binary Search

Hints

The exact-match binary search template almost works — what should happen when the target isn't found?
Track the smallest index where `nums[index] >= target` as you narrow the range.
When the loop ends, `lo` is exactly that insertion index.

Approach

Use the same halving template, but instead of returning -1 on a miss, keep narrowing: if `nums[mid] < target`, move `lo = mid + 1`; otherwise `hi = mid - 1`. When the loop ends (`lo > hi`), `lo` is the first index where `nums[lo] >= target` — exactly the correct insertion point, whether or not the target is present.

Java solution

Solution.java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return lo;
    }
}

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