33. Search Insert Position

Binary search for the first index whose value is >= target. That index is the answer whether or not the target is present: if present it's the target's position, otherwise it's exactly where the target belongs.

Idea

We want the leftmost position where target could sit while keeping the array sorted — the classic lower bound. Binary search converges on the first index i with nums[i] >= target. If target exists, that's its index; if not, that's the gap it should fill.

Using a half-open range [lo, hi) with hi = len(nums) lets the answer be len(nums) (append at the end) without special-casing.

Algorithm

1. lo = 0, hi = len(nums).
2. While lo < hi:
   • mid = (lo + hi) // 2.
   • If nums[mid] < target, the answer is to the right → lo = mid + 1.
   • Else (nums[mid] >= target), mid might be the answer → hi = mid.
3. Return lo (== hi).

Worked example: nums = [1,3,5,6], target = 5

• lo=0, hi=4, mid=2 → nums[2]=5, not < 5 → hi=2.
• lo=0, hi=2, mid=1 → nums[1]=3 < 5 → lo=2.
• lo == hi == 2 → return 2 (nums[2] == 5).

For target = 2: converges to index 1 (between 1 and 3).

Complexity

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

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