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

Figure 10.12 Method that performs a binary search of an array already sorted in ascending order
After the array has been sorted, you can use a binary search to find values in the array very quickly— even when the array is extremely long. A sequential search takes an amount of time proportional to the array length. A binary search takes an amount of time proportional to the logarithm of the array length. When an array is very long, the difference between linear and logarithmic is huge. For example, suppose the length is 100,000. It works out that log2(100,000) 􏰀 17. Since 17 is about 6,000 times smaller than 100,000, binary search is approximately 6,000 times faster than sequential search for a 100,000-element array.
Note the binarySearch method in Figure 10.12, and, in particular, note its static modifier. You can use either an instance method or a class method to implement searching. In the previous subsection, we implemented searching with an instance method. This time, we implement searching with a class method, which is appropriate if you want a method to be used generically. To make it generic (that is, to make it usable by different programs), you should put the method in a separate class and make the method a class method. Since it’s a class method, different programs can call the binarySearch method eas- ily, using binarySearch’s class name, rather than using a calling object. For example, if you put the binarySearch method in a Utilities class, you would call binarySearch like this:
Utilities.binarySearch(
<array-name>, <number-of-filled-elements>, <searched-for-value>);
10.7 SearchinganArray 391
public static int binarySearch(
int[] array, int filledElements, int value)
{
}
// end binarySearch
int mid;
// index of middle element
// value of middle element
// index of lowest element
}
int midValue;
int low = 0;
int high = filledElements - 1; // index of highest element
while (low <= high)
{
mid = (low + high) / 2;
midValue = array[mid];
if (value == midValue)
// next midpoint
// and the value there
// found it!
// next time, use lower half
{
}
return mid;
else if (value < midValue)
{
}
else
{
high = mid - 1;
midA+p1a; go PDF /E/ nehxtatnimce,eruse // end while
upper half
}
low =
return -1;