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.