Sorting, Searching, and Merging - Advanced Topics in Java: Core Concepts in Data Structures - page 17

Suppose we were searching for 70 . The search will proceed as described above until we compare 70 with 66
(in location 7 ).

70 is bigger, we know that if 70 is in the list at all, it must be after position 7 , since the
numbers are in ascending order. In our next step, we confine our search to locations 8 to 8 .
This is just one location.

• Since

70 with item 8 , that is, 72 . Since 70 is smaller, we know that if 70 is in the list at
all, it must be before position 8 . Since it can't be after position 7 and before position 8 , we
conclude that it is not in the list.

• We compare

At each stage of the search, we confine our search to some portion of the list. Let us use the variables lo and hi
as the subscripts that define this portion. In other words, our search will be confined to num[lo] to num[hi] .
Initially, we want to search the entire list so that we will set lo to 0 and hi to 12 , in this example.
How do we find the subscript of the middle item? We will use the following calculation:

mid = (lo + hi) / 2;

Since integer division will be performed, the fraction, if any, is discarded. For example, when lo is 0 and hi is 12 ,
mid becomes 6 ; when lo is 7 and hi is 12 , mid becomes 9 ; and when lo is 7 and hi is 8 , mid becomes 7 .
As long as lo is less than or equal to hi , they define a nonempty portion of the list to be searched. When lo is
equal to hi , they define a single item to be searched. If lo ever gets bigger than hi , it means we have searched the
entire list and the item was not found.
Based on these ideas, we can now write a function binarySearch . To be more general, we will write it so that the
calling routine can specify which portion of the array it wants the search to look for the item.
Thus, the function must be given the item to be searched for ( key ), the array ( list ), the start position of the
search ( lo ), and the end position of the search ( hi ). For example, to search for the number 66 in the array num , above,
we can issue the call binarySearch(66, num, 0, 12) .
The function must tell us the result of the search. If the item is found, the function will return its location. If not
found, it will return -1 .

public static int binarySearch(int key, int[] list, int lo, int hi) {
//search for key from list[lo] to list[hi]
//if found, return its location; otherwise, return -1
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (key == list[mid]) return mid; // found
if (key < list[mid]) hi = mid - 1;
else lo = mid + 1;
}
return -1; //lo and hi have crossed; key not found
}

If item contains a number to be searched for, we can write code as follows:

int ans = binarySearch(item, num, 0, 12);
if (ans == -1) System.out.printf("%d not found\n", item);
else System.out.printf("%d found in location %d\n", item, ans);

If we want to search for item from locations i to j , we can write the following:

int ans = binarySearch(item, num, i, j);