< previous page page_664 next page >

Page 664
        else
            // Assert: item == list[middle]
            found = TRUE;
    }
    index = middle;
}
Let's do a code walk-through of this algorithm. The value being searched for is 24. Figure 12-7a shows the values of first, last, and middle during the first iteration. In this iteration, 24 is compared with 103, the value in list[middle]. Because 24 is less than 103, last becomes middle-1 and first stays the same. Figure 12-7b shows the situation during the second iteration. This time, 24 is compared with 72, the value in list[middle]. Because 24 is less than 72, last becomes middle-1 and first again stays the same.
In the third iteration (Figure 12-7c), middle and first are both 0. The value 24 is compared with 12, the value in list[middle]. Because 24 is greater than 12, first becomes middle+1. In the fourth iteration (Figure 12-7d), first, last, and middle are all the same. Again, 24 is compared with the value in list[middle]. Here 24 is less than 64, so last becomes middle-1. Now that last is less than first, the process stops; found is FALSE.
The binary search algorithm is the most complex algorithm that we have examined so far. The table below shows first, last, middle, and list[middle] for searches of 106, 400, and 406, using the same data as in the previous example. Go over the results shown in this table carefully.
item
first
last
middle
list[middle]
Termination of Loop
106
0
10
5
103
6
10
8
200
6
7
6
106
found = TRUE
400
0
10
5
103
6
10
8
200
9
10
9
300
10
10
10
400
found = TRUE
406
0
10
5
103
6
10
8
200
9
10
9
300
10
10
10
400
11
10
last < first
found = FALSE

 
< previous page page_664 next page >