Pattern this teaches:Binary Search on Sorted Data
Search Insert Position
An easy Binary Search interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Binary Search
- Sheets
- 1
- Core for
- 7 roles
The problem
A sorted array of distinct integers and a target are given. If the target is in the array, return its index; if not, return the index at which it would have to be placed to keep the array sorted.
Example 1
- Input
- nums = [2,4,7,9], target = 7
- Output
- 2
- Why
- 7 is already at index 2.
Example 2
- Input
- nums = [2,4,7,9], target = 3
- Output
- 1
- Why
- 3 would slot between 2 and 4, at index 1.
Example 3
- Input
- nums = [2,4,7,9], target = 11
- Output
- 4
- Why
- 11 is larger than everything, so it goes at the end, index 4.
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
How to think about it
Updated 2026-09-29The problem is finding the first index whose value is at least the target. When the target is missing, the binary search termination condition itself parks the lower boundary pointer at precisely the first position where the new value can sit without violating order.
Approaches, worst first
Linear search for threshold
time O(n) · space O(1)
Step sequentially through the array and stop at the first element greater than or equal to target, or return array length at the end. Predictable and correct, but ignores the ordering during navigation.
Lower-bound binary searchWrite this one
time O(log n) · space O(1)
Divide the interval repeatedly. When the middle value is strictly smaller than target, the answer must lie strictly to the right, advancing low to mid + 1. When the search exits, low holds the exact insertion slot.
Where people lose marks · 3
- Returning mid inside the loop handles exact matches but leaves the missed case ambiguous unless low is consistently returned when the loop terminates.
- Target exceeding all elements requires inserting at index n, which is an out-of-bounds index for reading; code that indexes nums[low] after the loop crashes.
- Using high as the fallback insertion index instead of low is off by one because high finishes to the left of the insertion point when pointers cross.
The theory behind it
Binary Search — the ground this problem stands on. All Binary Search problems
What Binary Search is
Binary search is the guessing strategy used when searching a thick telephone directory or guessing a secret number between one and a hundred. Rather than inspecting names one by one from the first page, the search opens straight to the middle page. If the target precedes that middle entry, the entire back half is discarded; if it follows, the front half is eliminated. Repeating this halved split finds the item with remarkable speed.
When to reach for it
Reach for binary search when queries target sorted collections, rotated sorted arrays, or monotonic answer spaces. Strong hints include logarithmic time constraints like O(log n) or search ranges exceeding one billion where stepping one value at a time times out. It also applies when validating whether a guessed solution is possible via a monotonic boolean check, known as binary search on answer.
How the pattern works
Define the search territory with two inclusive pointers, low and high. Compute the midpoint using low plus half the difference to high, avoiding integer overflow. Formulate an exact boolean condition that divides the range into true and false halves. Decide whether the boundary condition includes the midpoint or shifts strictly past it. The loop invariant states that the sought target, if it exists, remains trapped inside the interval throughout every iteration.
More Binary Search problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .