Skip to content
Laviyx Learn

Try

DSA course menu

Binary Search Explained: Iterative, Recursive and Boundary Searches

Learn binary search in Python: how halving gives O(log n), the iterative template, finding the first and last position of a value, the bisect module, and binary search on the answer.

Intermediate10 min readUpdated
On this page

Binary search finds a value in a sorted list by repeatedly halving the part that could contain it. Each comparison throws away half of what is left, so a million items need only about 20 comparisons: O(log n).

It is how you look up a word in a paper dictionary: open the middle, see whether your word comes before or after, and repeat in that half.

The iterative version#

Keep a range [low, high] that must contain the target if it is present:

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

numbers = list(range(0, 2_000_000, 2))       # 1,000,000 even numbers
print(binary_search(numbers, 1_234_568))
print(binary_search(numbers, 7))              # odd: not present
print(binary_search([3, 8, 15, 23, 42], 23))
Output
(617284, 17)
(-1, 20)
(3, 2)

A million items, found in at most 20 steps. A linear scan could need a million.

Printing the range on each step shows the halving:

Python
def trace(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        print(f"low={low} high={high} mid={mid} value={items[mid]}")
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(trace([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23))
Output
low=0 high=9 mid=4 value=16
low=5 high=9 mid=7 value=56
low=5 high=6 mid=5 value=23
5

Finding boundaries: first and last occurrence#

When values repeat, plain binary search returns some matching index. To find the first one, keep searching left after a match:

Python
def first_index(items, target):
    low, high, found = 0, len(items) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] >= target:
            if items[mid] == target:
                found = mid
            high = mid - 1         # keep looking left
        else:
            low = mid + 1
    return found

def last_index(items, target):
    low, high, found = 0, len(items) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] <= target:
            if items[mid] == target:
                found = mid
            low = mid + 1          # keep looking right
        else:
            high = mid - 1
    return found

data = [1, 2, 2, 2, 3, 5, 5, 8]
print(first_index(data, 2), last_index(data, 2))
print(first_index(data, 5), last_index(data, 5))
print(first_index(data, 4), last_index(data, 4))
Output
1 3
5 6
-1 -1

The number of times a value appears is last - first + 1, found in O(log n).

The bisect module#

Python's standard library already has these boundary searches. bisect_left returns the first position where the value could be inserted keeping the list sorted; bisect_right returns the position after any equal values:

Python
from bisect import bisect_left, bisect_right, insort

data = [1, 2, 2, 2, 3, 5, 5, 8]
print(bisect_left(data, 2), bisect_right(data, 2))
print(bisect_left(data, 4))          # where 4 would go

insort(data, 4)                       # insert keeping it sorted
print(data)
Output
1 4
5
[1, 2, 2, 2, 3, 4, 5, 5, 8]

insort finds the position in O(log n), but inserting into a list still shifts items, so it is O(n) overall.

Binary search on the answer#

Binary search works on any yes/no question that flips once: false, false, …, true, true. You do not even need a list.

Workers must ship packages (in order) within days days. What is the smallest daily capacity that works? If a capacity works, any larger one also works, so search the capacity:

Python
def days_needed(weights, capacity):
    days, load = 1, 0
    for w in weights:
        if load + w > capacity:
            days += 1
            load = 0
        load += w
    return days

def min_capacity(weights, days):
    low, high = max(weights), sum(weights)   # the answer is in this range
    while low < high:
        mid = (low + high) // 2
        if days_needed(weights, mid) <= days:
            high = mid           # mid works: try smaller
        else:
            low = mid + 1        # too small
    return low

packages = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(min_capacity(packages, 5))
print(days_needed(packages, 15), days_needed(packages, 14))
Output
15
5 6

With capacity 15 the packages fit in 5 days; 14 is not enough. The search tries about log₂(55 − 10) ≈ 6 capacities, each checked in O(n).

Common mistakes#

Practice#

Practice exercise

Write int_sqrt(n) that returns the largest whole number whose square is at most n, using binary search (no math.sqrt or ** 0.5).

Show hint

Search the range 0 to n. If mid * mid <= n, mid is a candidate and the answer may be bigger; otherwise it is smaller.

Show solution
Python
def int_sqrt(n):
    low, high, answer = 0, n, 0
    while low <= high:
        mid = (low + high) // 2
        if mid * mid <= n:
            answer = mid
            low = mid + 1
        else:
            high = mid - 1
    return answer

print([int_sqrt(n) for n in [0, 1, 8, 9, 15, 16, 1_000_000]])
Output
[0, 1, 2, 3, 3, 4, 1000]

Key takeaway#

Next: how lists get sorted in the first place, in Bubble, Selection and Insertion Sort.

Finished this lesson?

Related lessons

DSABig O Notation Explained Simply (With Python Examples)Learn Big O notation for beginners: what O(1), O(log n), O(n), O(n log n) and O(n²) mean, how to compare them, and the rules for simplifying Big O expressions.Beginner8 min readDSABubble Sort, Selection Sort and Insertion Sort in PythonLearn the three simple O(n²) sorting algorithms with Python code, step-by-step traces and comparison counts, plus what stable sorting means and when insertion sort is actually fast.Intermediate10 min readDSABinary Search Trees (BST) in Python: Insert, Search and DeleteLearn binary search trees: the BST property, searching and inserting in O(h), deleting nodes with zero, one or two children, validating a BST, and why unbalanced BSTs become slow.Intermediate15 min read

Recommended DSA resources

Some links are affiliate links. If you buy through them, Laviyx Learn may earn a commission at no extra cost to you. As an Amazon Associate, we earn from qualifying purchases.