LiveCodingInterview.com
← Articles

How to Implement Binary Search in Python

Python is one of the most common languages in coding interviews. If the input is sorted, binary search should be your reflex — and Python gives you both hand-rolled loops and a built-in `bisect` module.

For the full algorithm walkthrough (two methods, complexity, and interview variants), start with our Binary Search Algorithm guide.

Prerequisites

  • The array must be sorted in ascending order
  • Time complexity: **O(log n)** per query
  • Space: **O(1)** iterative, **O(log n)** recursive (call stack)

The standard interview template uses `lo` and `hi` pointers:

def binary_search(arr: list[int], x: int) -> int:
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if arr[mid] == x:
            return mid
        if arr[mid] > x:
            hi = mid - 1
        else:
            lo = mid + 1

    return -1

Use `lo + (hi - lo) // 2` instead of `(lo + hi) // 2` — interviewers appreciate overflow-safe midpoint math even though Python integers do not overflow.

Recursive version

def binary_search_recursive(arr: list[int], x: int, lo: int = 0, hi: int | None = None) -> int:
    if hi is None:
        hi = len(arr) - 1

    if lo > hi:
        return -1

    mid = lo + (hi - lo) // 2

    if arr[mid] == x:
        return mid
    if arr[mid] > x:
        return binary_search_recursive(arr, x, lo, mid - 1)
    return binary_search_recursive(arr, x, mid + 1, hi)

Prefer iterative in timed interviews — fewer stack concerns and easier to debug on a whiteboard.

Using bisect (production Python)

The standard library module `bisect` implements binary search on sorted lists:

import bisect

arr = [1, 3, 5, 7, 9]
x = 5

# Index where x would be inserted (leftmost)
idx = bisect.bisect_left(arr, x)
found = idx < len(arr) and arr[idx] == x

# bisect_right — insert after existing equal elements
idx_right = bisect.bisect_right(arr, x)

In interviews, write the loop yourself unless the interviewer explicitly allows library calls. In production code, prefer `bisect`.

Lower bound pattern

Find the first index where `arr[i] >= x`:

def lower_bound(arr: list[int], x: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

This template solves "first occurrence" and "insert position" problems. See the main binary search guide for when to use `lo <= hi` vs `lo < hi`.

Python-specific tips for interviews

  • Type hints (`list[int]`) are optional but show clarity
  • `//` is integer division — always use it for midpoints
  • List slicing (`arr[lo:hi]`) creates copies — **never slice** in binary search; move indices instead
  • Test empty list: `binary_search([], 1)` should return `-1`

Complexity

  • **Time:** O(log n) comparisons
  • **Space:** O(1) iterative, O(log n) recursive