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)

Worked example

Searching for 11 in the sorted array [2, 3, 7, 7, 11, 15, 25] (indices 0-6):

  • lo=0, hi=6: mid=3, arr[3]=7. 7 < 11, so lo becomes 4.
  • lo=4, hi=6: mid=5, arr[5]=15. 15 > 11, so hi becomes 4.
  • lo=4, hi=4: mid=4, arr[4]=11. Match — return index 4.

Three comparisons instead of a five-step linear scan. Trace this out loud in an interview before writing code; it confirms the loop invariant (the target, if present, always lies within [lo, hi]) and catches off-by-one mistakes before they hit the whiteboard.

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

  • Best case: O(1) — the target is at the first mid index checked
  • Average case: O(log n) comparisons
  • Worst case: O(log n) comparisons
  • Space: O(1) iterative, O(log n) recursive (call stack)