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, usemid = (low + high) / 2(round down). - If you set
low = mid, usemid = (low + high + 1) / 2(round up).