Language: Python
python
def binary_search(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid
else:
right = mid
return -1
Subtle one. Spot it before scrolling 👇
.
.
.
The bug: Infinite loop risk. When
arr[mid] < target, the code sets left = mid instead of left = mid + 1. If mid ends up equal to left again on the next iteration (which happens when the search space shrinks to 2 elements), the loop never makes progress.Fixed version:
python
def binary_search(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid
return -1
This is exactly why binary search is famously easy to get "almost right" but subtly wrong. Off-by-one errors here are so common that some engineers recommend writing out the invariant explicitly ("left is always a possible answer, right is always excluded") before coding it.
Do you write binary search from memory, or always double-check the boundaries? 👇