March 24
Binary Search
How to use sorted order to eliminate half the search space and keep a clear invariant.
Search Beginner 15 min TypeScript
Given an array of integers nums sorted in ascending order and an integer target, return the index of target if it exists. Otherwise return -1.
Example:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
What to notice before coding
- The array is sorted. That is the most important piece of information in the problem.
- Every comparison with the middle eliminates half of the remaining possible space.
- If the target does not exist, the search must finish with `-1`.
Common mistakes
- updating boundaries incorrectly and creating an infinite loop
- using `left < right` without understanding that it can miss the last candidate position
Step 1 — Write what you would do without sorting
Without sorted order, the baseline would be simple: inspect one element at a time.
That already helps you see the value of sorting.
The win of binary search is not just "moving faster."
The real win is:
eliminating half of the possibilities at every step.
Step 2 — Write the correct baseline
The most direct version is linear search:
export function search(nums: number[], target: number): number {
for (let index = 0; index < nums.length; index += 1) {
if (nums[index] === target) {
return index
}
}
return -1
}
It works, but it ignores the best clue in the prompt.
Step 3 — Ask what the middle tells you
If you inspect nums[mid]:
- if it equals the target, you are done
- if it is smaller, the whole left half becomes impossible
- if it is larger, the whole right half becomes impossible
That word "impossible" is the heart of the algorithm.
Step 4 — Keep a still-valid interval
Use two bounds:
left: first still-possible positionright: last still-possible position
While left <= right, at least one candidate remains.
When the middle fails, discard the impossible half by moving the bounds.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function search(nums: number[], target: number): number {
// your solution here
return -1
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(log n)
Space: O(1)
Solution 1 — Linear search O(n)
It works, but it does not use the sorted order.
export function search(nums: number[], target: number): number {
for (let index = 0; index < nums.length; index += 1) {
if (nums[index] === target) {
return index
}
}
return -1
}Solution 2 — Binary search O(log n)
Now the sorted order becomes real elimination of search space.
export function search(nums: number[], target: number): number {
let left = 0
let right = nums.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
const value = nums[mid]
if (value === target) {
return mid
}
if (value < target) {
left = mid + 1
continue
}
right = mid - 1
}
return -1
}The important part is not memorizing the loop. It is keeping the candidate interval coherent.
What to say in the interview
A strong short explanation would be:
The linear baseline costs
O(n). Since the array is sorted, every comparison with the middle lets me eliminate half of the remaining interval. I keep[left, right]as the set of candidate indexes and move the bounds until I find the target or exhaust the interval.
That shows that you:
- used the right signal from the prompt
- explained the algorithm as an invariant
- reduced the chance of boundary bugs from pure memorization
When this pattern shows up again
The same pattern comes back when you need to:
- search inside ordered space
- eliminate half the possibilities
- maintain valid bounds
- justify why a whole region became impossible
The point is not memorizing binary search.
The point is learning to think in terms of a candidate interval.