SINGLE-DIMENSIONAL ARRAYS - Introduction to Java Programming: Comprehensive Version - page 267

You now know how the binary search works. The next task is to implement it in Java.
Don't rush to give a complete implementation. Implement it incrementally, one step at a time.
You may start with the first iteration of the search, as shown in Figure 7.10a. It compares the
key with the middle element in the list whose low index is 0 and high index is list.length
- 1 . If key < list[mid] , set the high index to mid - 1 ; if key == list[mid] , a match
is found and return mid ; if key > list[mid] , set the low index to mid + 1 .
Next consider implementing the method to perform the search repeatedly by adding a loop,
as shown in Figure 7.10b. The search ends if the key is found, or if the key is not found when
low > high .
When the key is not found, low is the insertion point where a key would be inserted to
maintain the order of the list. It is more useful to return the insertion point than -1 . The
method must return a negative value to indicate that the key is not in the list. Can it simply
return -low ? No. If the key is less than list[0] , low would be 0 . -0 is 0 . This would indi-
cate that the key matches list[0] . A good choice is to let the method return -low - 1 if the
key is not in the list. Returning -low - 1 indicates not only that the key is not in the list, but
also where the key would be inserted.

why not - 1?

key is 11

low mid high

key 50 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

list 2 4 7 10 11 45 50 59 60 66 69 70 79

low mid high

[0] [1] [2] [3] [4] [5]

key 7 list 2 4 7 10 11 45

low mid high

[3] [4] [5]

key 11 list 10 11 45

F IGURE 7.9

Binary search eliminates half of the list from further consideration after each

comparison.

public static int binarySearch(
int [] list, int key) {
int low = 0 ;
int high = list.length - 1 ;

public static int binarySearch(
int [] list, int key) {
int low = 0 ;
int high = list.length - 1 ;

while (high >= low) {
int mid = (low + high) / 2 ;
if (key < list[mid])
high = mid - 1 ;
else if (key == list[mid])
return mid;
else
low = mid + 1 ;
}

int mid = (low + high) / 2 ;
if (key < list[mid])
high = mid - 1 ;
else if (key == list[mid])
return mid;
else
low = mid + 1 ;

return -1 ; // Not found

} }

(b) Version 2

(a) Version 1

F IGURE 7.10

Binary search is implemented incrementally.