Python ProgrammingLevel: Intermediatepython

How Binary Search Works in Python (With Code You Can Run)

Prepared by the Assignment Achievers computer science team.

Free Educational Resource

Problem Statement / Assignment Scope

You're given a list of integers `nums`, sorted in ascending order, and a value `target`. Write a function that returns the index of `target` if it's in the list and `-1` if it isn't. Your solution has to run in O(log n) time.

Prerequisites: Comfortable with Python lists and indexes, while loops, and the idea of a function calling itself.

Step-by-Step Worked Solution

1. The idea

Because the list is sorted, one comparison with the middle value tells you which half the target must be in. Throw away the other half and repeat. Each step halves the work, which is what makes binary search a divide and conquer algorithm.

2. Tracing the loop

Start with the whole list: left = 0 and right = len(nums) - 1.
Find the middle: middle = left + (right - left) // 2.
Compare:
- Equal to the target? Return middle.
- Smaller than the target? The answer is further right, so move left to middle + 1.
- Larger than the target? The answer is further left, so move right to middle - 1.
Stop when the range is empty: once left > right, the target isn't there, so return -1.

Searching for 56 in the example list checks 48 first (too small), then 71 (too big), then 56: three comparisons instead of five.

3. How fast is it?

Time: O(1) if the middle element is the target straight away, and O(log n) on average and in the worst case, because the range halves every pass.
Space: O(1) for this loop version. A recursive version uses O(log n) because each call adds a frame to the call stack.

solution.pypython

def binary_search(nums: list[int], target: int) -> int:
    """
    Find target in a sorted list by repeatedly halving the range.
    Time: O(log n)   Extra space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        # Middle of the current range (this form also avoids overflow in other languages)
        middle = left + (right - left) // 2

        if nums[middle] == target:
            return middle
        if nums[middle] < target:
            left = middle + 1   # target can only be to the right
        else:
            right = middle - 1  # target can only be to the left

    return -1  # range is empty: target isn't in the list


if __name__ == "__main__":
    marks = [12, 25, 37, 48, 56, 71, 89]
    print(binary_search(marks, 56))  # 4
    print(binary_search(marks, 50))  # -1

Key Takeaways & Core Principles

Binary search only works on sorted data; on an unsorted list its answers are meaningless.
The loop version needs no extra memory, which is why it's usually preferred over recursion.
Writing `middle = left + (right - left) // 2` is a habit worth keeping for languages with fixed-size integers.
Halving the range each time gives O(log n), far quicker than checking every element on large lists.

Frequently Asked Questions

Why must the list be sorted?

The algorithm decides which half to discard by assuming everything to the left of the middle is smaller and everything to the right is larger. Without sorting, that assumption fails and the target can be thrown away by mistake.

Does Python have binary search built in?

Yes. The `bisect` module (`bisect_left`, `bisect_right`) uses binary search to find where a value belongs in a sorted list. Your course may still ask you to write it yourself to show you understand it.

Academic References & Standards

[1]Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. Source Link

Help With Your Own Task

Got a Similar Question for Your Course?

Send it to an Assignment Achievers expert. You'll get an original answer that follows your brief and rubric, the working shown step by step, and a free originality report.