Python ProgrammingLevel: Intermediatepython

Binary Search Algorithm in Python: Complete Step-by-Step Guide

Reviewed by Dr. Alan Myers, Ph.D. in Computer Science, University of Cambridge.

Free Educational Resource

Problem Statement / Assignment Scope

Given a sorted array of integers `nums` and an integer `target`, write a function to search for `target` in `nums`. If `target` exists, return its index. Otherwise, return `-1`. The algorithm must run with O(log n) runtime complexity.

Prerequisites: Understanding of Python lists, basic indexing, while loops, and recursion fundamentals.

Step-by-Step Worked Solution

1. Algorithmic Principle

Binary search relies on the Divide and Conquer paradigm. Because the input sequence is pre-sorted, we can eliminate half of the remaining elements in each step by comparing the middle element directly against the target value.

2. Step-by-Step Execution Walkthrough

Boundary Initialization: Set two pointers: low = 0 and high = len(nums) - 1.
Midpoint Calculation: Compute mid = low + (high - low) // 2 to avoid overflow in large arrays.
Conditional Comparison:
- If nums[mid] == target, search completes successfully; return mid.
- If nums[mid] < target, target lies in the right partition. Narrow range by setting low = mid + 1.
- If nums[mid] > target, target lies in the left partition. Narrow range by setting high = mid - 1.
Termination Condition: If low > high without finding the target, return -1.

3. Complexity Breakdown

Time Complexity: Best case O(1), Average & Worst case O(log n) because the search domain is halved with every iteration.
Space Complexity: O(1) for the iterative implementation; O(log n) for recursive calls due to the call stack frame allocation.

solution.pypython

def binary_search_iterative(nums: list[int], target: int) -> int:
    """
    Performs iterative binary search on a sorted array.
    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    low, high = 0, len(nums) - 1

    while low <= high:
        # Prevent potential integer overflow with integer midpoint
        mid = low + (high - low) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Verification / Test Suite
if __name__ == "__main__":
    test_array = [-1, 0, 3, 5, 9, 12]
    print(f"Index of 9: {binary_search_iterative(test_array, 9)}")   # Output: 4
    print(f"Index of 2: {binary_search_iterative(test_array, 2)}")   # Output: -1

Key Takeaways & Core Principles

Input array must be sorted for binary search to yield valid results.
Iterative approach is preferred in production due to O(1) auxiliary memory footprint.
Use `mid = low + (high - low) // 2` to avoid integer overflow issues common in typed languages.
Binary search executes in logarithmic O(log n) time, drastically outperforming O(n) linear search on large datasets.

Frequently Asked Questions

Why does binary search require a sorted array?

Without a sorted order, eliminating half of the elements after inspecting the midpoint is impossible because you cannot guarantee whether values to the left are smaller or larger than the target.

How does binary search compare to Python's built-in bisect module?

Python's standard library includes the `bisect` module (`bisect_left`, `bisect_right`), which uses the exact same C-optimized binary search algorithm for locating insertion points.

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

Custom Academic Guidance

Need a Custom Solution for Your Specific Assignment?

Our verified Ph.D. subject experts deliver 100% original, rubric-compliant assistance with Turnitin reports and step-by-step explanations.