Prerequisite

The input must be sorted ascending. Binary search exploits ordering to halve the search space each step — if the list isn’t sorted, the whole premise collapses.

assert li == sorted(li), "list must be sorted"

Correct Implementation

def bin_search(li, v, l, h):
    if l >= h:
        return -1

    mid = l + (h - l) // 2

    if li[mid] == v:
        return mid
    elif li[mid] > v:
        return bin_search(li, v, l, mid)     # v in left half, [l, mid)
    else:
        return bin_search(li, v, mid + 1, h) # v in right half, [mid+1, h)

What Your Code Got Wrong

Your version had one critical bug that breaks everything:

mid = int((h - l) / 2)      # ❌ BUG: missing l +
mid = l + (h - l) // 2       # ✅ correct

Without adding l, every recursive call computes mid relative to 0 instead of the current low bound. Trace bin_search(li, 11, 3, 7):

Call l h (h-l)//2 l+(h-l)//2 (correct)
1st 0 7 3 3
2nd 3 7 2 5

Your mid index jumped backward, so the algorithm no longer halves — it wanders.

Common Logic Misunderstandings

1. Off-by-one in the recursive calls

Use exclusive upper bound (h = len(li), not len(li) - 1):

Branch Correct range Call
v < li[mid] left half = [l, mid) bin_search(li, v, l, mid)
v > li[mid] right half = [mid+1, h) bin_search(li, v, mid+1, h)

The right half starts at mid + 1 because mid was already checked. If you pass mid instead, you risk infinite loops when h - l == 1.

2. Stopping condition

if l >= h:   # correct — no elements left to check
if mid < 0 or mid >= len(li):  # wrong — still recurses when search space is empty

The proper base case checks whether the range [l, h) is empty, not whether mid has escaped the array.

3. Integer division

int((h - l) / 2) → works but fragile. Prefer // 2 — cleaner and explicitly integer.

Iterative Version (no recursion)

Often simpler to reason about:

def bin_search(li, v):
    l, h = 0, len(li)
    while l < h:
        mid = l + (h - l) // 2
        if li[mid] == v:
            return mid
        elif li[mid] > v:
            h = mid
        else:
            l = mid + 1
    return -1

Edge Cases to Test

Case Expected
Empty list [] -1
One element, found [5] search 5 0
One element, not found [5] search 3 -1
Two elements [1, 3] search 1 or 3 0 or 1
Value smaller than all [2,5,7] search 1 -1
Value larger than all [2,5,7] search 9 -1
Duplicates [1, 3, 3, 3, 5] search 3 any valid index (not all)

Complexity

  • Time: O(log n) — halves the search space each step.
  • Space: O(log n) recursive, O(1) iterative.