My Learning
Binary Search
Learning objectives
What you'll understand
Explain why binary search requires ordered data.
Trace the left, right and middle boundaries of a search.
Implement iterative binary search.
Recognize its logarithmic time complexity.
Lesson
The core idea
Binary search finds a value by repeatedly cutting the remaining search space in half. Instead of checking every item, it compares the target with the middle value and immediately discards the half that cannot contain the answer.
The data must be ordered before ordinary binary search can make this decision safely.
Think in boundaries
Keep two boundaries: left and right. The middle index sits between them. If the middle value is smaller than the target, move the left boundary forward. If it is larger, move the right boundary backward.
Why it is efficient
Each comparison removes roughly half of the remaining possibilities. A search space of 1,024 elements therefore needs only around 10 reductions in the worst case.
Typical iterative binary search runs in O(log n) time and O(1) auxiliary space.
Example
Iterative binary search
function binarySearch(
values: number[],
target: number,
) {
let left = 0
let right = values.length - 1
while (left <= right) {
const middle = Math.floor(
(left + right) / 2,
)
if (values[middle] === target) {
return middle
}
if (values[middle] < target) {
left = middle + 1
} else {
right = middle - 1
}
}
return -1
}Key takeaways
Binary search depends on ordered data.
Each decision removes half of the remaining search space.
Move left or right boundaries based on the middle value.
Its logarithmic growth makes it efficient for large ordered collections.