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

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

FIGURE 14-14 Search list, list[6]...list[11]

The above process is now repeated on the list list[6]...list[11] , which is a list of
length 6 .
Because we frequently need to determine the middle element of the list, the binary search
algorithm is usually implemented for array-based lists. To determine the middle element of
the list, we add the starting index, first , and the ending index, last , of the search list and
divide by 2 to calculate its index. That is, mid = first þ last

2 .
Initially, first = 0 and (because the array index in Java starts at 0 and listLength
denotes the number of elements in the list) last = listLength - 1 . (Note that the
formula for calculating the middle element works regardless of whether the list has an
even or odd number of elements.)
The following Java method implements the binary search algorithm. If the search item
is found in the list, its location is returned. If the search item is not in the list, -1 is
returned.

public static int binarySearch( int [] list, int listLength,
int searchItem)

{

int first = 0;
int last = listLength - 1;
int mid;

boolean found = false ;

while (first <= last && !found)
{

mid = (first + last) / 2;

if (list[mid] == searchItem)
found = true ;
else if (list[mid] > searchItem)
last = mid - 1;

else

first = mid + 1;

}