How binary search worksHow it works
Keep two pointers, left and right, around the part of the array that could still hold the target. Look at the middle element. If it matches, you are done. If the target is smaller, throw away the right half; if it is bigger, throw away the left half. Repeat until the range is empty.
Find 23 in a sorted array
function binarySearch(nums: number[], target: number): number {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // not found
}Why left + (right − left) / 2?Core idea
(left + right) / 2 can overflow (go past the largest integer the language can store) when both are large. left + (right - left) / 2 gives the same middle but never adds two big numbers together.
Variation: first occurrencePattern
With duplicates, finding a match is not enough; you often need the first one. When you find the target, remember it and keep searching to the left.
function findFirst(nums: number[], target: number): number {
let left = 0, right = nums.length - 1, result = -1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
result = mid;
right = mid - 1; // keep searching left
} else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}More variationsPattern
Search in a rotated arrayone half sorted
A sorted array rotated at some point, like [4, 5, 6, 7, 0, 1, 2]. One half around mid is always sorted: check which one, then decide which side can hold the target.
Binary search on the answermonotonic
When a yes/no check flips only once as the answer grows (for example, “can we ship all packages in D days with capacity C?”), binary search over possible answers instead of over the array.
Common mistakesPitfalls
In the interviewIn the interview
Stating the invariant (the rule that stays true every loop) is what makes your bounds easy to trust.
Frequently asked questionsFAQ
Why is the midpoint written as left + (right - left) / 2?
That form avoids integer overflow when left and right are very large indices. Computing (left + right) / 2 first can exceed the maximum representable integer and wrap to a negative value, producing a wrong midpoint. The subtraction form is mathematically identical but stays within range, so it is always safe to use regardless of index size.
What is binary search on the answer and when is it used?
Binary search on the answer searches over a range of possible solutions instead of over array elements. It works when the answer space is monotonic: if a candidate value is feasible, larger values are feasible too, and if it is infeasible, smaller values are. You write a feasibility check, then binary search the smallest feasible value. Common cases include minimum shipping capacity and maximum minimum distance.
How do you find the first or last position of a value in a sorted array with duplicates?
On a match, do not return immediately. For the first occurrence, record the index and then narrow right to mid minus 1, continuing the search left. For the last occurrence, record the index and narrow left to mid plus 1, continuing right. Either way the loop keeps shrinking, so total time stays O(log n) even with many duplicates.
Now explain binary search to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.