Binary search finds a target in a sorted sequence by repeatedly discarding half of the remaining search range. It is efficient for large sorted arrays, but the sorted-order requirement is essential. Applying binary search to unsorted data can produce an incorrect result even when the code runs without an error.
How binary search works
Start with the left and right ends of the search range and inspect the middle element. If it equals the target, the search is complete. If the target is smaller, continue in the left half; if it is larger, continue in the right half.
The algorithm terminates when the target is found or when the search range becomes empty. Each comparison reduces the remaining range substantially.
Work through a small example
Suppose the sorted list is [3, 7, 11, 18, 24, 31, 42] and the target is 24. Check the middle value 18 first. Since 24 is larger, discard the left half and search the upper portion. The next middle check can locate 24.
The exact middle index depends on the chosen low/high calculation. Both common variants work when the range updates are consistent.
def binary_search(items: list[int], target: int) -> int:
low, high = 0, len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid
if items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
values = [3, 7, 11, 18, 24, 31, 42]
print(binary_search(values, 24)) # 4Time and space complexity
Binary search runs in O(log n) time because the search interval is approximately halved on every iteration. An iterative implementation uses O(1) auxiliary space aside from the input. A recursive version uses additional call-stack space proportional to recursion depth.
A linear search runs in O(n) time and works on unsorted sequences. Binary search is not automatically faster for every real-world task: sorting data has a cost, data structure operations matter, and a small list may not justify the extra complexity.
Common off-by-one errors
Incorrect range conditions can skip the first or last element or create an infinite loop. With inclusive bounds, while low <= high is a common pattern, and the bound updates use mid - 1 and mid + 1. With half-open ranges, the condition and updates must follow a different consistent convention.
Test values at the first and last positions, a target in the middle, a target smaller than every value, a target larger than every value, and an empty list.
- The input must be sorted according to the comparison being used.
- Use consistent inclusive or half-open boundary conventions.
- Return a clear not-found value such as -1 or None.
- Test empty lists and boundary targets.
- Consider duplicate values if the task requires the first occurrence rather than any match.
When binary search is a good choice
Binary search is useful when data is sorted and can be accessed by index efficiently, such as an array. Variants are also used to find lower bounds, thresholds and positions in monotonic search spaces.
In technical interviews, explain the sorted-input assumption, loop invariant, termination condition and complexity. Being able to explain why each discarded half cannot contain the target matters as much as memorizing the code.
Understanding the concept is the first step.
Explore related resources or learn about subject-focused tutoring designed to help you understand the material.