Binary search finds a target value in a sorted data structure by repeatedly comparing the target with the middle element and discarding the half that cannot contain it. This continues until the target is found or the remaining search interval is empty.
The Binary Search Mechanism
Binary search uses three index variables: low, high, and mid. Initially, low identifies the first element and high identifies the last element.
The middle index is calculated using:
The algorithm then follows one of three cases:
| Comparison | Action |
|---|---|
| Target equals the middle value | Return mid; the target has been found. |
| Target is less than the middle value | Set high to mid minus 1, discarding the upper half. |
| Target is greater than the middle value | Set low to mid plus 1, discarding the lower half. |
For example, search for 19 in [3, 7, 12, 19, 24, 31, 40]:
| Step | Search interval and decision |
|---|---|
| 1 | The middle value is 19. It equals the target. |
| Result | Return index 3, assuming indexing begins at 0. |
If the target were 31, the first comparison with 19 would discard the lower half. The next middle value would be 31, so the algorithm would return index 5.
A typical iterative version is:
low = 0
high = length(array) - 1
while low <= high
mid = (low + high) DIV 2
if array[mid] = target
return mid
else if target < array[mid]
high = mid - 1
else
low = mid + 1
return NOT_FOUND
Because the search space is halved after each comparison, binary search has time complexity . A linear search, by comparison, has time complexity .
IB Exam Technique
For B2.4 Programming algorithms, state that the data must already be sorted, trace changes to low, high, and mid accurately, and explain why one half is discarded. A common misconception is that binary search works on any list; it does not work correctly unless the values are ordered.
