SEARCHING AND SORTING - Java Programming: From Problem Analysis to Program Design - page 917

of key comparisons and item assignments, the user can decide which algorithm to use in a
particular situation.

Binary Search
A sequential search is not efficient for large lists. It typically still searches about half the
list. However, if the list is sorted, you can use another search algorithm, called a
binary search. A binary search is much faster than a sequential search, but a binary
search can be performed only on a sorted list. A binary search uses the divide and
conquer technique to search the list. First, the search item is compared with the middle
element of the list. If the search item is not equal to the middle element, and is less
than the middle element of the list, the search is restricted to the first half of the list;
otherwise, the second half of the list is searched.
Consider the following sorted list of length 12 , shown in Figure 14-12.

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]
list 4

8 19 25 34 39 45 48 66 75 89 95

FIGURE 14-12 List of length 12

Suppose that we want to determine whether 75 is in the list. Initially, the entire list is the
search list (see Figure 14-13).

search list

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

list 4 8 19 25 34 39 45 48 66 75 89 95

mid

FIGURE 14-13 Search list, list[0]...list[11]

First, we compare 75 with the middle element, list[5] (which is 39 ), in the list.
Because 75 / list[5] and 75 > list[5] , next we restrict our search to the list
list[6]...list[11] , as shown in Figure 14-14.

1
4