Page 426 - Introduction to Programming with Java: A Problem Solving Approach

392 Chapter 10 Arrays and ArrayLists
In the binarySearch method call, note the array argument. Being a class method, binarySearch cannot access instance variables. More specifically, it cannot access the searched array as an instance vari- able. So the searched array must be passed in as an argument. This allows the method to be used from out- side its class.
Split up a problem into smaller problems.
Before examining the code details in the binarySearch method, let’s discuss the ba- sic strategy—divide and conquer. You first identify the middle element in the sorted array. You then figure out whether the searched-for value goes before or after the middle element. If it belongs before the middle element, you narrow the search range to the lower half of the array (the half with the smaller-indexed elements). If, on the other hand, the searched-for
value belongs after the middle element, you narrow the search range to the upper half of the array. You then repeat the process. In other words, within the narrowed-down half of the array, you identify the middle ele- ment, figure out whether the searched-for value belongs before or after the middle element, and narrow the search range accordingly. Every time you do this, you cut the problem in half, and this enables you to zero in quickly on the searched-for value—if it’s there at all. Splitting the array in half is the “divide” part of “di- vide and conquer.” Finding the searched-for value within one of the halves is the “conquer” part.
Now let’s see how the binarySearch method implements the divide-and-conquer algorithm. The method declares mid, low, and high variables that keep track of the indexes for the middle element and the two elements at the ends of the array’s search range. For an example, see the left drawing in Figure 10.13. Using a while loop, the method repeatedly calculates mid (the index of the middle element) and checks whether the mid element’s value is the searched-for value. If the mid element’s value is the searched-for value, then the method returns the mid index. Otherwise, the method narrows the search range to the low half or the high half of the array. For an example of that narrowing process, see Figure 10.13. The method repeats the loop until either the sAeaprchaedg-for valuPeDisFfoundEornthhe saeanrchcraengre shrinks to the point where low’s index is greater than high’s index.
value 4
array array array low0low0 0
1mid1 1 low
2 high 2 mid 2
-6
-2
4
18
21
22
30
-6
-2
4
18
21
22
30
-6
-2
4
18
21
22
30
filledElements
7mid3 3 3
444
555 high 6 6 6
99 99 99
high
Figure 10.13 Example execution of Figure 10.12’s binarySearch method