The Self-Taught Computer Scientist

10
12
13
14
15
18
19
Figure 3.1: Sorted data set for a binary search

---

Introduction to Algorithms
28
Your first step in a binary search is to locate the middle number. There are seven items in this list, 
so the middle number is 14 (Figure 3.2).
Since 14 is not the number you are searching for, you continue.
The next step is to determine whether the number you are looking for is greater than or less than 
the middle number. The number you are looking for, 19, is greater than 14, so there is no need to 
search the bottom half of the list. You can get rid of it. Now all that is left is the upper half of the list 
with three numbers left to search (Figure 3.3).
Next, you repeat the process by locating the middle number again, which is now 18 (Figure 3.4).
Since 18 is not the number you are searching for, you again determine whether you keep the lower 
half or upper half of the list. Because 19 is greater than 18, you keep the upper half and eliminate the 
lower half.
That leaves only one number, 19, which is the number you are searching for (Figure 3.5). If the 
number were not 19, you would know it is not in the list.
10
12
13
14
15
18
19
Figure 3.2: A binary search first locates the 
middle number.
15
18
19
Figure 3.3: The next step in a 
binary search eliminates the half of 
the data that cannot contain 
the number.
15
18
19
Figure 3.4: A binary search then 
finds the middle number again.

---