Algorithms
Binary Search (Intro)
Difficulty: Beginner
Searching a sorted array of one billion elements with linear search takes up to a billion comparisons. Binary search needs about thirty. The same input, the same hardware, two algorithms with completely different scaling behavior,...
Binary Search (Intro)
Searching a sorted array of one billion elements with linear search takes up to a billion comparisons. Binary search needs about thirty. The same input, the same hardware, two algorithms with completely different scaling behavior, separated only by the assumption that the array is sorted.
Binary Search (Intro) explains how to get that speedup and how to write the algorithm without the off-by-one errors and infinite loops that trip up almost everyone the first time. You will implement the canonical two-pointer template with left and right indices, learn why mid = left + (right - left) / 2 matters for avoiding integer overflow, and trace the algorithm step by step on small inputs to see the search space halve each iteration. The lesson also surveys built-in support across languages (Array.indexOf is not a binary search; Python's bisect is) and the most common pitfalls.
In Arrays & Strings, you saw why indexed access on an array is O(1); binary search is the first algorithm that uses that property to skip past whole regions instead of walking through them. Big-O Notation (Upper Bound) gave you the language O(log n) and the reasoning that explains why halving leads to logarithmic growth.
From here you will move into Two Pointers (Intro), which generalizes the same coordinated-index idea beyond exact-match searching.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain why binary search requires sorted data and how it achieves O(log n) time.
Implement binary search iteratively in JavaScript and Python, handling all edge cases.
Calculate the midpoint safely using `mid = left + Math.floor((right - left) / 2)` to avoid integer overflow.
Trace through binary search step by step, tracking left, right, and mid pointers.
Identify and fix common binary search bugs: off-by-one errors, infinite loops, and incorrect comparisons.
Compare binary search with linear search and explain when each is appropriate.
Why This Matters
01
Binary search reduces a linear O(n) search to O(log n) — for a million elements, that is 20 comparisons instead of a million.
02
It is one of the most frequently tested algorithms in coding interviews and appears in problems across every difficulty level.
03
The divide-and-conquer intuition behind binary search is the foundation for binary search trees, balanced trees, and many advanced algorithms.
04
Real-world systems — databases, search engines, operating systems — rely on binary search and its variants for fast lookups.
Key Terms
8 terms you'll encounter in this lesson
Binary search
A search algorithm that finds a target in a sorted array by repeatedly comparing the middle element and halving the search space. Runs in O(log n) time.
Search space
The portion of the array that could still contain the target. Binary search halves this range with each comparison.
Midpoint
The index at the center of the current search space, calculated as left + floor((right - left) / 2).
Left pointer (lo)
The lower bound of the current search space. Moves right when the target is greater than the middle element.
Right pointer (hi)
The upper bound of the current search space. Moves left when the target is less than the middle element.
O(log n)
Logarithmic time complexity — the number of operations grows proportionally to the logarithm of the input size. Halving n repeatedly takes log2(n) steps.
Integer overflow
A bug where (left + right) exceeds the maximum integer value. Avoided by computing mid = left + (right - left) / 2 instead of (left + right) / 2.
Off-by-one error
A common binary search bug where the loop condition or pointer update is off by one index, causing missed elements or infinite loops.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Binary search works on unsorted arrays"
Binary search requires the array to be sorted. If arr[mid] > target, binary search eliminates the right half — but this is only correct if all elements to the right are also greater than arr[mid], which is only guaranteed in a sorted array.
"Calculating mid as (left + right) / 2 is always safe"
In languages with fixed-size integers (Java, C++), left + right can overflow. The safe formula is mid = left + (right - left) / 2. In JavaScript and Python, integers can grow arbitrarily, so overflow is not a practical concern — but using the safe formula is a good habit.
"Binary search always finds the element in exactly log n steps"
O(log n) is the worst case. In the best case (target at the midpoint), binary search finds the element in 1 comparison — O(1). On average it takes about log n comparisons.
"Using left < right instead of left <= right is equivalent"
They are NOT equivalent. With left <= right, the search checks the case where left equals right (a single-element range). With left < right, that element is skipped. The wrong choice leads to missed elements or infinite loops depending on how you update the pointers.