Computer Program Reading Comprehension Project
U of T Computer Program Reading Comprehension Project
Topics | Index | Exercises | Search | About | Help | Contact Us
Binary Search
This exercise helps explain the binary search algorithm, which is an efficient method of searching for elements within a sorted array.

Download files: binSearch.java
Areas: Searching algorithms.


binSearch.java
1public static int binSearch (double[] list, double item) {
2
3  int bottom = 0;
4  int top = list.length - 1;
5  int middle;
6  boolean found = false;
7  int location = -1;
8
9  while (bottom <= top && !found) {
10
Displaying 10 of 25 lines
View full source


Question 1
Suppose the array list has at least one element. When are list[bottom] and list[top] respectively the first and the last elements of the array list?
Solution

Question 2
What is the significance of the boolean variable found?
Solution

Question 3
Why is location initialized to -1?
Solution

Question 4
bottom .. top is an index range of the array list. How is it related to item, the value we are looking for in the array?
Hints Solution

Question 5
The while loop has two conditions. The first condition is bottom <= top. What is the purpose of this condition?
Solution

Question 6
The while loop has two stopping conditions. The second loop condition is !found. What is the purpose of this condition?
Solution

Question 7
In binary search, the middle element is compared with the item that we are searching for. What happens next?
Solution

Question 8
If the middle element is less than the item, we need to continue searching in the second half of the search range bottom .. top. How are the variables bottom and top used to do this?
Solution

Question 9
If you are asked to perform binary search on an array that is stored in descending order, what changes would you make to the original code?
Solution

Question 10
Consider the following array of doubles:

1.0     3.0     7.0     8.0     11.0     16.0     21.0     25.0

If we search for the number 3.0 in this array using the binary search algorithm, how many times will the while loop execute?
Solution

Question 11
If list.length = n, what is the order of time complexity of the binary search algorithm in terms of n?
Hints Solution