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.

Example 1:

Input: nums = [2, 6, 10, 14], target = 10
Output: 2

Example 2:

Input: nums = [2, 6, 10, 14], target = 4
Output: 1

Example 3:

Input: nums = [2, 6, 10, 14], target = 20
Output: 4

Example 4:

Input: nums = [2, 6, 10, 14], target = 0
Output: 0

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

Solution Breakdown

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=4 in [2,6,10,14]: mid=1, nums[1]=6 > 4 so high=0; mid=0, nums[0]=2 < 4 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.