< _

Binary Search Explained With Examples

Abstract generated cover for Binary Search Explained With Examples.

Binary search is an algorithm for finding a target value in sorted data. The important word is **sorted**. Binary search works by repeatedly cutting the search space in half. Instead of checking every item one by one, it looks at the middle and decides which half can be ignored. That makes it much faster than linear search for large sorted lists. Binary search is a great algorithm to learn early because it teaches a useful pattern:

Use information about the data to avoid unnecessary work.

The Mental Model

Imagine guessing a number between 1 and 100. If you guess randomly, you may need many attempts. If you guess intelligently, you start in the middle: ```plain text 50

If the answer is higher, you ignore 1 through 50.
Then you guess the middle of 51 through 100:
```plain text
75

Each guess cuts the remaining possibilities in half. That is binary search.

The Requirement: Sorted Data

Binary search only works when the data is sorted. This is valid:

numbers = [2, 5, 8, 12, 16, 23, 38]

This is not:

numbers = [12, 2, 38, 5, 16, 8, 23]

If the list is not sorted, the middle value does not tell you which half to ignore. That is the core rule.

Linear Search First

Here is a simple linear search:

def linear_search(numbers, target):
    for index, number in enumerate(numbers):
        if number == target:
            return index
    return -1

This checks items one by one. In the worst case, it checks the whole list. That is O(n). For small lists, linear search is often fine. For large sorted lists, binary search can be much better.

Binary Search in Python

Here is an iterative binary search:

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2
        guess = numbers[middle]

        if guess == target:
            return middle

        if guess < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

Usage:

numbers = [2, 5, 8, 12, 16, 23, 38]

print(binary_search(numbers, 16))  # 4
print(binary_search(numbers, 7))   # -1

The function returns the index if the target exists. Otherwise, it returns `-1`.

Walking Through the Algorithm

Search for `16` in:

[2, 5, 8, 12, 16, 23, 38]

Start: ```plain text left = 0 right = 6 middle = 3 numbers[3] = 12

The guess is \`12\`.
\`12\` is less than \`16\`, so the target must be to the right.
Move \`left\`:
```plain text
left = 4
right = 6
middle = 5
numbers[5] = 23

The guess is `23`. `23` is greater than `16`, so the target must be to the left. Move `right`: ```plain text left = 4 right = 4 middle = 4 numbers[4] = 16

Found it.
Instead of checking every item, binary search used the sorted order to remove half the possibilities each time.
## Why Binary Search Is Fast
Binary search is O(log n).
That means it grows slowly as the input gets larger.
For a list of 1,000,000 sorted items, binary search needs around 20 checks in the worst case.
That is the power of repeatedly halving the search space.
## Common Mistakes
### Mistake 1: Using binary search on unsorted data
This is the most important mistake.
Binary search requires sorted data. If the data is not sorted, the algorithm's decisions are meaningless.
### Mistake 2: Getting the loop condition wrong
This condition is common:
```python
while left <= right:

If you use the wrong condition, you may skip the final possible item or create an infinite loop. Binary search is simple conceptually, but the boundaries need care.

Mistake 3: Forgetting to move past the middle

When the guess is too low:

left = middle + 1

When the guess is too high:

right = middle - 1

If you write `left = middle` or `right = middle`, the search may get stuck.

Where This Shows Up in Real Projects

Binary search appears in more places than direct list searching. You may see the same idea in:

  • searching sorted arrays
  • finding insertion positions
  • database indexes
  • version debugging with "good" and "bad" commits
  • optimization problems
  • guessing thresholds The broader pattern is useful: when the answer space is ordered, you can often cut it in half repeatedly.

Python's Built-In Tools

Python has a module called `bisect` for binary-search-style operations.

import bisect

numbers = [2, 5, 8, 12, 16, 23, 38]

index = bisect.bisect_left(numbers, 16)
print(index)  # 4

You should still learn how binary search works manually. But in production code, built-in tools are often safer than rewriting the algorithm yourself.

Key Takeaways

  • Binary search finds values in sorted data.
  • It repeatedly cuts the search space in half.
  • Binary search is O(log n).
  • It is much faster than linear search for large sorted lists.
  • Boundary updates are the main implementation detail to get right.

  • Python's `bisect` module is useful for real code.

    Related Articles

  • Big O Notation Explained With Python Examples

  • Arrays Explained: Indexing, Searching, and Updating
  • Recursion Explained With Simple Examples

← Back to Blog Index