Search Insert Position

Problem

Sorted indexes and autocomplete systems need fast insertion-point lookup to maintain order. Given a sorted array of distinct integers and a target, return the index of the target if it exists, or the index where it would be inserted to keep the array sorted.

Input: nums = [1, 3, 5, 6], target = 5  → 2
Input: nums = [1, 3, 5, 6], target = 2  → 1
Input: nums = [1, 3, 5, 6], target = 7  → 4
Input: nums = [1, 3, 5, 6], target = 0  → 0

Solution

Approach - exact-match binary search, returning the converged left pointer when the target is absent.

Run the standard skeleton: low = 0, high = len(nums) - 1, loop while low <= high. Each step take mid = low + (high - low) // 2 and compare. If nums[mid] == target you return mid immediately. If nums[mid] < target, every index up to and including mid is too small, so you discard the left half with low = mid + 1. If nums[mid] > target, mid is too large, so high = mid - 1. The insight is what low represents when the loop ends. Every low = mid + 1 move steps low past values strictly less than target, and low never moves past a value >= target. So low is always the leftmost index where nums[i] >= target - which is precisely the position the target would occupy to keep the array sorted. That is why you can return low after the loop without any extra bookkeeping. Trace target=2 in [1,3,5,6]: mid=1, nums[1]=3 > 2 so high=0; mid=0, nums[0]=1 < 2 so low=1; now low > high, return low=1, the correct insert slot.

Edge cases - target larger than every element leaves low == len(nums) (insert at the end); target smaller than every element keeps low == 0 (insert at front); a single-element array resolves in one comparison either way.

Complexity - O(log n) time, O(1) space - the window halves each iteration and only pointers are stored.