Binary Search
Maintained by Vikas D, software engineer
You are handed an array of numbers that is guaranteed to be sorted from smallest to largest, along with a single target value to locate.
If the target sits somewhere in the array, report the index where it lives. If it never appears, report -1 instead.
Because the input is already ordered, you can do far better than scanning every element. The order lets you discard half of the remaining candidates with each comparison.
Each value in the array is distinct, so there is at most one correct index to return.
Examples
The value 9 sits at index 4, so that index is returned.
No element equals 2, so the search reports -1.
A single-element array whose only value matches the target returns index 0.
Constraints
- The array is sorted in strictly ascending order.
- All values are unique, so at most one index can match.
- The array may be empty, in which case the answer is -1.
- Values can be negative, zero, or positive integers.
Visible test cases
- search([-1,0,3,5,9,12], 9) == 4
- search([-1,0,3,5,9,12], 2) == -1
- search([5], 5) == 0
Hints
Hint 1
A plain left-to-right scan works and is easy to get right, but it ignores the fact that the array is sorted.
Hint 2
Track a low and a high bound for the slice that could still contain the target, then look at the middle element of that slice.
Hint 3
If the middle value is too small, the answer can only be to its right; if too large, only to its left. Move the matching bound and repeat until the bounds cross.
Approaches
Linear scan
Time O(n) · Space O(1)Walk through every element and compare it to the target, ignoring the sort.
- Loop over each index from start to end.
- Return the index the moment an element equals the target.
- If the loop finishes with no match, return -1.
Binary search
Time O(log n) · Space O(1)Keep a candidate window and halve it each step by comparing the target to the middle element.
- Set low to 0 and high to the last index.
- While low does not pass high, compute the middle index as low plus half the gap (this avoids overflow on large bounds).
- If the middle value equals the target, return that middle index.
- If the middle value is smaller than the target, move low to one past the middle; otherwise move high to one before the middle.
- When the window empties, return -1.
Common mistakes
- Computing the middle as (low + high) / 2 can overflow in fixed-width languages; use low + (high - low) / 2 to stay safe.
- Using low < high instead of low <= high skips checking the final single-element window and misses matches there.
- Forgetting to move the bound past the middle (writing low = mid rather than low = mid + 1) can spin in an infinite loop.
- Returning the value at the index instead of the index itself.
Follow-up variations
- If duplicates were allowed, return the first or last index of the target rather than any index.
- Return the insertion point where the target would go if it is missing, instead of -1.
- Adapt the search to an array that was sorted then rotated at an unknown pivot.
- Find the smallest value greater than or equal to the target (a lower-bound query).