The Classic Binary Search Loop and Its Bounds
18 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Looking for one order among a million sorted orders by reading from the start takes a million steps. Binary search takes about twenty. The loop is short, and almost every bug in it is an off-by-one in the bounds.
Throw away half at every look
Binary search finds a value in a sorted list by comparing with the middle item and discarding the half that cannot hold it. It needs O(log n) steps instead of O(n).
A phone book is searched by opening the middle page, not page one. If the name comes later, the whole first half is gone. Binary search does the same on a sorted list.
Example 1 · Brute force: scan from the start
orders = [4, 9, 15, 22, 31, 47, 58, 63, 71, 90]target = 63looks = 0for position, order_id in enumerate(orders): looks += 1 if order_id == target: breakprint("found at", position, "after", looks, "looks")found at 7 after 8 looks
What this code does
- The scan checks every item in turn, so the worst case is n looks: O(n) time.
- It ignores that the list is sorted, which is the information binary search uses.
The loop with lo, hi and mid
The search window is the range lo..hi of positions that can still hold the target. Every round must make it strictly smaller, or the loop never ends.
Keep a window lo..hi that may still hold the target. Look at the middle item. Too small: move lo past it. Too big: move hi before it. Equal: done.
def binary_search(items, target): lo, hi = 0, len(items) - 1 while lo <= hi: mid = (lo + hi) // 2 if items[mid] == target: return mid if items[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
print(binary_search([4, 9, 15, 22, 31, 47, 58, 63, 71, 90], 63))7
Example 2 · Binary search with a trace
def binary_search(items, target): lo, hi = 0, len(items) - 1 while lo <= hi: mid = (lo + hi) // 2 print("lo", lo, "hi", hi, "mid", mid, "value", items[mid]) if items[mid] == target: return mid if items[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
orders = [4, 9, 15, 22, 31, 47, 58, 63, 71, 90]print("answer", binary_search(orders, 63))print("answer", binary_search(orders, 50))lo 0 hi 9 mid 4 value 31 lo 5 hi 9 mid 7 value 63 answer 7 lo 0 hi 9 mid 4 value 31 lo 5 hi 9 mid 7 value 63 lo 5 hi 6 mid 5 value 47 lo 6 hi 6 mid 6 value 58 answer -1
What this code does
- Searching for 63 needs 2 looks instead of 8. Searching for 50 shrinks the window until it is empty and returns -1.
- Time is O(log n) and extra space is O(1), because the loop only keeps three numbers.
The window shrinks every round, and mid itself is never kept: it was checked, so the next window starts at mid + 1 or ends at mid - 1. When lo passes hi, the window is empty and the target is not there.
Closed or half-open bounds
Closed bounds keep hi on the last position and loop while lo <= hi. Half-open bounds put hi one past the end and loop while lo < hi. Pick one style and keep every line consistent with it.
def binary_search_half_open(items, target): lo, hi = 0, len(items) while lo < hi: mid = (lo + hi) // 2 if items[mid] < target: lo = mid + 1 else: hi = mid return lo if lo < len(items) and items[lo] == target else -1
print(binary_search_half_open([4, 9, 15, 22, 31, 47, 58, 63, 71, 90], 63))7
Example 3 · How slowly the number of looks grows
for size in [10, 1000, 1_000_000, 1_000_000_000]: lo, hi = 0, size - 1 looks = 0 while lo <= hi: mid = (lo + hi) // 2 looks += 1 lo = mid + 1 print(size, "items need at most", looks, "looks")10 items need at most 4 looks 1000 items need at most 10 looks 1000000 items need at most 20 looks 1000000000 items need at most 30 looks
What this code does
- Always moving right is the worst case, because the window never ends early.
- A billion items need only 30 looks. That is why O(log n) is so powerful.
Here hi = mid keeps mid in the window because it might be the answer, so the loop condition is lo < hi. Mixing hi = mid with lo <= hi is the classic infinite loop.
No overflow, and the bisect shortcut
Python integers grow as needed, so (lo + hi) // 2 can never overflow. In Java or C++ it can, so interviewers still ask for lo + (hi - lo) // 2. For everyday work, bisect already holds the loop.
from bisect import bisect_left
prices = [120, 250, 400, 650, 900]spot = bisect_left(prices, 650)print(spot)print(spot < len(prices) and prices[spot] == 650)3 True
Example 4 · Recursive version and the bisect check
from bisect import bisect_left
def search(items, target, lo, hi): if lo > hi: return -1 mid = lo + (hi - lo) // 2 if items[mid] == target: return mid if items[mid] < target: return search(items, target, mid + 1, hi) return search(items, target, lo, mid - 1)
prices = [120, 250, 400, 650, 900]print(search(prices, 650, 0, len(prices) - 1))print(search(prices, 300, 0, len(prices) - 1))spot = bisect_left(prices, 650)print(spot < len(prices) and prices[spot] == 650)3 -1 True
What this code does
- The recursive form passes the window as arguments. It uses O(log n) stack space, so the loop is the better default.
- The form
lo + (hi - lo) // 2is the overflow-safe middle that interviewers expect, even though Python does not need it.
Example 5 · Search records by their id
from bisect import bisect_left
students = [(101, "Asha"), (104, "Ravi"), (107, "Meena"), (110, "Kiran")]roll_numbers = [roll for roll, _ in students]spot = bisect_left(roll_numbers, 107)if spot < len(students) and roll_numbers[spot] == 107: print(students[spot][1])Meena
What this code does
- The list of ids is built once and is already sorted, so bisect can search it.
- The position found in the ids is the position of the record in the original list.
bisect_left returns the position where the target is or would go. Check that the position holds the target to turn it into a yes or no.
Next step
Check your understanding
10 quick questions