Binary Search

EasyalgorithmsBinary search

Maintained by Vikas Dulgunde, 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

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9

Output: 4

The value 9 sits at index 4, so that index is returned.

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2

Output: -1

No element equals 2, so the search reports -1.

Input: nums = [5], target = 5

Output: 0

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.

Loading the editor...

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).

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9

Output: 4

The value 9 sits at index 4, so that index is returned.

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2

Output: -1

No element equals 2, so the search reports -1.

Input: nums = [5], target = 5

Output: 0

A single-element array whose only value matches the target returns index 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).

Binary Search

Examples

Constraints

Hints

Approaches

Linear scan

Binary search

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Binary Search

Examples

Constraints

Hints

Approaches

Linear scan

Binary search

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep