Textbook
Binary search finds an exact-match index in an array sorted in nondecreasing order. This implementation uses integerOpens in a new tab elements and an integerOpens in a new tab target. The function returns one matching index or −1 if no match exists; it does not promise the first or last index among duplicates.
The variables left and right store inclusive bounds. The invariant is that if the target exists and has not been found, at least one matching index remains in the current range. The middle index is floorOpens in a new tab((left + right) / 2). If its value is below the target, every index through the middle can be excluded, so left becomes middle + 1. A greater value symmetrically makes right become middle − 1.
Sorted order proves each exclusion safe. Every unsuccessful step strictly shrinks the range, ensuring termination. When left > right, the range is empty; the invariant then implies there is no match. An empty array starts in this state.
For an array of length $n\ge2$, worst-case time is $O(\log n)$ under constant-cost comparisons and indexed access. The iterative version stores a fixed number of variables, using $O(1)$ extra space. Checking or establishing the original sorted order is not included.
A nonempty range contains right − left + 1 positions. After an unsuccessful comparison, at most the floorOpens in a new tab of half that many remain, because the middle itself is excluded. This connects termination with the logarithmicOpens in a new tab step bound. Keeping the source list unchanged matters to the argument: rearranging elements or changing their order during the search can invalidate the safety of previously discarded halves.
In plain language
In an ordered phone book, comparison with the middle name immediately rules out half the pages. The middle entry itself is excluded after comparison, or the search can reopen the final page forever and call it perseverance. Two bookmarks track the remaining interval, so there is no need to remember every inspected entry. The ordering must remain intact throughout the search; pages rearranged between steps terminate the phone book’s contract without notice.
Example
The target is 17 in the sorted illustrative array [2, 5, 8, 12, 17, 23, 31]. Indices start at zero. The steps below follow the same algorithm as the code.
Binary search in Python
Initial range
The left bound is 0 and the right bound is 6. All seven positions remain possible.
Step 1 of 4: Initial range
Read all steps
Initial range
The left bound is 0 and the right bound is 6. All seven positions remain possible.
- Values
- 25812172331
- Bounds
- left = 0currentright = 6current
The middle value is 12
Index 3 contains 12, below 17. Indices 0–3 are excluded; left = 4.
- Values
- 2excluded5excluded8excluded12current172331
- Remaining
- 17included23included31included
The middle value is 23
Within indices 4–6, the middle is index 5. Its value 23 exceeds the target, so right = 4.
- Values
- 2excluded5excluded8excluded12excluded1723current31excluded
- Remaining
- 17included
A match
Both bounds meet at index 4. Its value 17 matches the target: the result is 4.
- Values
- 2excluded5excluded8excluded12excluded17included23excluded31excluded
- Index
- 4included
For the absent target 18, the first exclusions leave the same index 4 containing 17. The next comparison advances left to 5 while right remains 4, and the function returns −1. That value signals absence rather than a usable result index: Python index −1 would select the list’s last element. Using numbers[index] requires a prior check that a match was found.
def binary_search(numbers: list[int], target: int) -> int:
left = 0
right = len(numbers) - 1
while left <= right:
middle = (left + right) // 2
value = numbers[middle]
if value == target:
return middle
if value < target:
left = middle + 1
else:
right = middle - 1
return -1
numbers = [2, 5, 8, 12, 17, 23, 31]
print(binary_search(numbers, 17)) # 4
print(binary_search(numbers, 18)) # -1The binary_search function accepts a sorted list numbers and a target, returns an index or −1, and does not mutate the list. For an empty input, right is −1 and the loop never runs. Searching for absent 18 eventually empties the range; a one-element input needs at most one middle-element check.
Finding duplicate boundaries, searching a rotated array, and finding the minimumOpens in a new tab feasible value change the half-selection rule. Those cases are covered in the paid material “Binary Search in Python”. Its product page lists the contents and current access terms.