Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Binary Search

Explore the binary search algorithm to efficiently locate elements in sorted lists by repeatedly halving the search space. Understand the iterative and recursive implementations in Python, their time and space complexity, and when to apply this technique for faster searching compared to linear search.

We'll cover the following...

When the data is sorted, you no longer need to check every element one by one. Binary search eliminates half the remaining candidates at each step, which makes it much faster than linear search on large datasets.

Real-world intuition

Imagine Maple Street now has a sorted apartment block. The flats are numbered in ascending order (for example, 1, 3, 5, 9, 13, 21, 34, 47, 56, 72). You need to find flat 21.

Because the flats are ordered, you do not need to check every door one by one. Instead, using the building directory (or floor plan), you can check the middle flat, look at its number, and ask: Is the flat you are looking for on the left or the right?

Based on the middle value, you either find the target or discard half of the remaining flats. If you check the middle flat (13) and you are looking for 21, all flats to the left (1, 3, 5, 9, 13) are smaller and cannot be the target. So, you discard that half and continue searching only in the right half (21, 34, 47, 56, 72).

Each step cuts the remaining search space in half. Searching in a block of 1,024 flats takes at most 10 steps. Searching in a block of 1,000,000 flats takes at most 20 steps. This is the power of binary search.

Binary search repeatedly divides the search space in half by comparing the target with the middle element. It discards the half that cannot contain the target and continues until the target is found or the search space is empty.

Critical precondition: Binary search depends on order. If the data is not sorted (ascending or descending), eliminating half the search space can incorrectly eliminate the target.

How it works

Binary search works on a sorted list (typically in ascending order) and, in its iterative form, uses three pointers: low, high, and mid.

  • low is the index of the leftmost element still under consideration.

  • high is the index of the rightmost element still under consideration.

  • mid is computed as the midpoint of the current window: mid = (low + high) // 2.

At each step, the algorithm compares arr[mid] with the target and takes one of three actions:

  1. If arr[mid] == target, the search is ...