Binary search is a powerful and efficient algorithm, but it’s also easy to make mistakes when implementing it. Whether you’re a beginner or an experienced programmer, these errors can lead to incorrect results or even infinite loops. In this article, we’ll explore the most common mistakes in binary search and provide practical tips on how to avoid them. By the end, you’ll be able to write bug-free binary search implementations with confidence.
Prerequisite: Binary Search Algorithm: Pseudocode and Explanation
Incorrect Loop Condition
Using the wrong loop condition, such as low < high instead of low <= high, can cause the algorithm to miss the target if it’s at the low or high index.
For example:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low < high: # Incorrect condition
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
To fix this, use low <= high to ensure the algorithm checks all possible positions, including when low and high are equal.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high: # Correct condition
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Integer Overflow
Calculating mid as (low + high) // 2 can cause integer overflow in languages with fixed-size integers (e.g., C++, Java) when low and high are very large.
For example:
mid = (low + high) // 2 # Potential overflow in some languages
To avoid this, use mid = low + (high - low) // 2.
mid = low + (high - low) // 2 # Safe calculation
Updating Pointers Incorrectly
Updating low or high incorrectly, such as setting high = mid instead of high = mid - 1, can lead to infinite loops or incorrect results.
For example:
if arr[mid] < target:
low = mid + 1
else:
high = mid # Incorrect update
Always update low to mid + 1 or high to mid - 1 to ensure the search range shrinks properly.
if arr[mid] < target:
low = mid + 1
else:
high = mid - 1 # Correct update
Forgetting to Sort the Input
Binary search only works on sorted lists. Forgetting to sort the input can lead to incorrect results.
For example:
arr = [23, 5, 16, 12, 2, 38, 56, 72, 91]
target = 23
result = binary_search(arr, target) # Incorrect result
Always sort the list before performing binary search.
arr = [23, 5, 16, 12, 2, 38, 56, 72, 91]
arr.sort() # Sort the list
target = 23
result = binary_search(arr, target) # Correct result
Handling Duplicate Elements
If the list contains duplicate elements, binary search may return any occurrence of the target, which might not be the desired behavior.
For example:
arr = [2, 5, 8, 12, 12, 12, 23, 38]
target = 12
result = binary_search(arr, target) # May return any index of 12
If you need the first or last occurrence, modify the algorithm accordingly. For example, to find the first occurrence:
def binary_search_first(arr, target):
low = 0
high = len(arr) - 1
result = -1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == target:
result = mid
high = mid - 1 # Continue searching the left half
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
Edge Cases
Failing to handle edge cases, such as an empty or null list.
For example:
arr = []
target = 5
result = binary_search(arr, target) # May raise an error
Explicitly handle edge cases at the beginning of the function.
def binary_search(arr, target):
if not arr: # Handle empty or null list
return -1
low = 0
high = len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Summary
Use low <= high to ensure all positions are checked. Calculate mid as low + (high - low) // 2 to avoid overflow. Always update low to mid + 1 or high to mid - 1. Ensure the list is sorted before performing binary search. Modify the algorithm to handle first/last occurrences if needed. Handle empty lists and out-of-range targets explicitly.