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)

Binary search vs. linear scan and hash lookup

A linear scan is O(n) but needs no sort and no extra memory - fine for an unsorted list or a one-off search. A hash map lookup is O(1) average but costs O(n) to build and only tells you whether a value is present, not where it sits relative to its neighbors. Reach for binary search when both are true: the data is already sorted (or sorting it once is cheap relative to the number of queries you'll run), and you need position information - first index >=, count of elements less than, closest value - that a hash map cannot give you.

FAQ

Can you binary search a linked list?

Not efficiently, because binary search needs O(1) random access to the midpoint; a singly or doubly linked list only gives O(n) access to an arbitrary node, which erases the O(log n) advantage. If the underlying data is a linked list, copy it into an array first, or use a structure built for ordered access with O(log n) lookup, like a skip list or balanced BST.

How does binary search handle duplicate values?

The iterative and recursive templates above return any matching index, not necessarily the first or last one. Use bisect_left (or the lower_bound template) to find the first occurrence, and bisect_right minus one to find the last. This distinction is exactly what "find first and last position of an element in a sorted array" interview questions test.

Does binary search work on non-numeric data?

Yes, as long as the data has a total order and is sorted by it - strings compare lexicographically, dates compare chronologically. bisect accepts a key= function (Python 3.10+) to search a custom order without pre-computing it, and custom objects need __lt__ defined (or a key function) since arr[mid] > x relies on comparison, not equality.

Should I use bisect or write the loop myself?

In production code, use bisect - it's tested, handles duplicates and edge cases correctly, and signals to reviewers that you know the standard library. In an interview, write the loop yourself unless told otherwise; interviewers are checking that you understand the invariant (what lo, hi, and mid mean and when each moves), which bisect hides.