Polymorphism - Java Software Solutions: Foundations of Program Design - page 518

To search the remaining candidates, we once again examine the “middle” ele-
ment. The middle element is 72, and thus we have still not found the target. But
once again, we can eliminate half of the viable candidates (those greater than 72)
and we are left with:

Viable Candidates

0
10

1
12

2
18

3
22

4
31

5
34

6
40

7
46

8
59

9
67

10
69

11
72

12
82

13
84

14
98

Employing the same approach again, we select the middle element, 67, and
find the element we are seeking. If it had not been our target, we would have
continued with this process until we either found the value or eliminated all
possible data.
With each comparison, a binary search eliminates approximately half of the
remaining data to be searched (it also eliminates the middle element as well). That is,
a binary search eliminates half of the data with the first comparison, another quarter
of the data with the second comparison, another eighth of the data with the third
comparison, and so on. The binary search approach is pictured in Figure 10.5.
The binarySearch method from the Searching class performs a binary search
by looping until the target element is found or until the viable candidates drop to
zero. Two integer indexes, min and max , are used to define the portion of the array
that is still considered viable. When min becomes greater than max , then the viable
candidates have been exhausted.
On each iteration of the loop, the midpoint is calculated by dividing the sum of
min and max by two. If there are currently an even number of viable candidates,
and thus two “middle” values, this calculation discards the fractional remainder
and picks the first of the two.
If the target element is not found, the value of min or max is modified to elimi-
nate the appropriate half of the viable candidates. Then the search continues.

start

FIGURE 10.5 A binary search