Imagine looking for a particular card in a large collection. Checking every card might take a while. If the cards are in order, you can check one near the middle instead: that comparison tells you which half cannot contain the card. Binary search repeats this move on the half that remains. It works because the sequence is sorted. section 1.5 section 3.7
For a sorted array, keep track of the range where the target could still be:
- Start with left at the first index and right at the last. Inspect the middle element. section 3.7
- If the middle element matches, return its index. If it is larger than the target, move right just before the middle; otherwise, move left just after it. section 3.7
- Repeat until you find a match or left passes right. An empty remaining range means the target is absent. section 3.7
def binary_search(self, target):
left = 0 #1
right = self._size - 1
while left <= right:
mid_index = (left + right) // 2
mid_val = self._array[mid_index]
if mid_val == target:
return mid_index #2
elif mid_val > target:
right = mid_index - 1 #3
else:
left = mid_index + 1 #4
return None #5
#1 Initially, the target can be in the whole array.
#2 We found the position of the target.
#3 The target can only be in the left half.
#4 The target can only be in the right half.
#5 If it gets here, the target is not in the array.
The Python implementation shows the two boundary indices, the middle-index calculation, and the return value for an unsuccessful search. Boundary updates are easy to get wrong, so test the method thoroughly. section 3.7
An unsuccessful binary search. After one comparison, we have ruled out more than half of the array. After two, more than 75% of it is excluded. In this example, by the third comparison, when we have only two elements where our target could be, we discover that the target is not in the array.
This unsuccessful search illustrates the payoff: one comparison rules out more than half the array, and a second rules out more than three-quarters before the search establishes that the target is absent. section 3.7
Halving the remaining range gives binary search O(log(n)) time and O(1) additional space, compared with O(n) time for linear search. The catch is maintaining sorted order: insertions and deletions take extra effort. A sorted array is therefore especially useful when searches greatly outnumber changes. A sorted linked list does not offer the same benefit, because reaching its middle requires traversal rather than direct indexed access. section 4.15 section 3.8 section 6.13
One detail matters when values repeat: this basic method returns a match, not necessarily the first or last occurrence. Adapt the search only when a particular occurrence is required. section 3.7
