Search Insert Position

Explanation & Solution

Description

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be inserted in order.

You must write an algorithm with O(log n) runtime complexity.

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

Output: 2

Explanation: 5 is found at index 2.

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

Approach

Modified Binary Search pattern

1. Initialize Pointers

Set left = 0 and right = nums.length (note: right is one past the end to handle insertion at the end).

2. Binary Search Loop

While left < right, compute mid = (left + right) >> 1.
If nums[mid] < target, the insert position is to the right → left = mid + 1.
Otherwise, the insert position is at mid or to the left → right = mid.

3. Return Insert Position

When the loop ends, left is the correct index where the target is found or should be inserted.

🧠 Key Insight

This is a classic left-bound binary search that finds the leftmost index where nums[index] >= target.

Time

O(log n)standard binary search.

Space

O(1)only pointer variables.

Visualization

Input:

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

—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone

7 steps

Solution Code

Median of Two Sorted Arrays

Time Based Key-Value Store