Infinite Loops

Consider searching with low = mid instead of low = mid + 1:

while low < high:
    mid = (low + high) / 2
    if condition:
        high = mid
    else:
        low = mid  // WRONG!

If low = 5, high = 6, then mid = 5. If condition is false, low = 5. The loop never terminates.

Fix: When narrowing to the right, use low = mid + 1. Or use mid = (low + high + 1) / 2 (round up) when setting low = mid.

Rule of thumb:

• If you set high = mid, use mid = (low + high) / 2 (round down).
• If you set low = mid, use mid = (low + high + 1) / 2 (round up).