Programming and Problem Solving with Java

(^556) | Array-Based Lists
item : fish
First
Second
Third
item : snake
First
Second
Third
Fourth
item : zebra
First
Second
Third
Fourth
Fifth
Iteration
10
10
7
10
10
10
10
10
10
10
10
10
last
0 6 6 0 6 9
10
0
6
9
10
11
first
5 8 6 5 8 9
10
5
8
9
10
middle
found is true
found is true
last < first
Terminating
Condition
dog
horse
fish
dog
horse
rat
snake
dog
horse
rat
snake
listItems[middle]
Table 11.2 Binary Searching
Average Number of Iterations
Length Sequential Search Binary Search
10 5.5 2.9
100 50.5 5.8
1,000 500.5 9.0
10,000 5000.5 12.0
because the list is cut in half each time through the loop.The following table compares a sequential
search and a binary search in terms of the average number of iterations needed to find an item:
If the binary search is so much faster, why not use it all the time? It certainly is faster in
terms of the number of times through the loop, but it requires more computations within the
binary search loop than in the other search algorithms. Thus, if the number of components
in the list is small (say, less than 20), the sequential search algorithms are faster because they
perform less work at each iteration. As the number of components in the list increases, the
binary search algorithm becomes relatively more efficient.
Here is the code for isTherethat uses the binary search algorithm:
public booleanisThere(String item)
// Returns true if item is in the list; false otherwise
// Binary search algorithm is used
// Assumption: List items are in ascending order