Binary Search Algorithm Explained (Time Complexity + Code)

The binary search algorithm is the fastest way to find an item in a sorted list, and one of the first algorithms every computer science student learns. It's also an interview favourite, because it's short to write but easy to get subtly wrong.

In this guide you'll see how binary search works step by step, why its time complexity is O(log n), working code in Python, Java and C++, and a memory trick so you never forget the rules.

Try it first: the guessing game

Before any theory, play this. You're about to watch binary search beat you at a game.

That's binary search. The computer never guessed randomly; it always picked the middle of what was left, so every answer cut the possibilities in half.

What is binary search?

Binary search is a searching algorithm that finds a target value in a sorted array by repeatedly dividing the search range in half. It compares the target with the middle element:

• If they're equal, you're done.
• If the target is bigger, it can only be in the right half, so ignore the left.
• If the target is smaller, it can only be in the left half, so ignore the right.

How binary search works, step by step

1. Set two pointers: low at the first index and high at the last.
2. While low ≤ high, find the middle: mid = (low + high) / 2 (rounded down).
3. If arr[mid] equals the target, return mid.
4. If arr[mid] is smaller than the target, set low = mid + 1.
5. Otherwise, set high = mid - 1.
6. If low passes high, the target isn't there: return -1.

Binary search code (Python, Java, C++)

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid            # found: return the index
        elif arr[mid] < target:
            low = mid + 1         # target is in the right half
        else:
            high = mid - 1        # target is in the left half
    return -1                     # not found

nums = [3, 7, 11, 15, 19, 24, 28, 33, 41]
print(binary_search(nums, 24))   # 5
print(binary_search(nums, 50))   # -1

Binary search time complexity

Every comparison halves the remaining items. Starting from n items, after k steps you have n / 2ᵏ left. You're done when that reaches 1, so k = log₂(n). That's why binary search is O(log n). (New to this notation? Read Big O notation explained.)

To feel how fast that is: linear search through a billion sorted items could take a billion comparisons. Binary search needs about 30.

Linear search vs binary search

• Linear search: works on any list, checks items one by one, O(n).
• Binary search: needs sorted data, halves the range each step, O(log n).
• If you search an unsorted list only once, linear search is fine. If you search many times, sort once (see our sorting algorithms guide) and binary search after.

What to learn next

Binary search is the foundation for binary search trees and many “search on the answer” interview problems. Next, learn the two everyday data structures in stack vs queue.

Frequently asked questions