Binary Search Java Code
1 int[] data;
2 int size;
3
4 public boolean binarySearch(int key)
5 {
6 int low = 0;
7 int high = size - 1;
8
9 while(high >= low) {
10 int middle = (low + high) / 2;
11 if(data[middle] == key) {
12 return true;
13 }
14 if(data[middle] < key) {
15 low = middle + 1;
16 }
17 if(data[middle] > key) {
18 high = middle - 1;
19 }
20 }
21 return false;
22 }
Explanation:
- line 1: tells us that we have an array of integers called
data. An array is just an ordered list of values, just
like the list we talked about in our algorithm. An integer is a
positive or negative whole number.
- line 2: size tells us the number of items that we have in the
list.
- lines 4, 5, and 22: These lines tell us that the code between line 5
and 22 performs one task, and give the name binarySearch
to the task. key is the target item that we will search
for in data. The word boolean tells us that
linearSearch will return true if it finds the key
in the list, and it will return false if the key is not in
the list.
- line 6: low is the variable that tells us where the beginning
of the remaining list is, and we give it an initial value of 0.
- line 7: high is the variable that tells us where the end
of the remaining list is, and we give it an initial value of the
last thing in the list.
- line 9: This line tells us to keep going until low is bigger than or
equal to high.
- line 10: middle we calculate so we can divide the list into
two pieces.
- line 11, 12, 13: We found the key, so we return true.
- line 14, 15, 16: If the item in the middle of the list is less than
our key, we should look for the key in the top half of the list, so
we calculate a new value for low.
- line 17, 18, 19: If the item in the middle of the list is greater than
our key, we should look for the key in the bottom half of the list, so
we calculate a new value for high.
- line 21: If we get to this line then we know that the key is not in
the list so we return false.
Karen Reid
Last modified: Thu Mar 2 17:28:56 EST 2000