## CS 101 (Spring 1999) Quiz 10: Arrays and Binary Search

Quiz Posted
(Wednesdays)
Given in class
(Wednesdays)
7 Apr 14 Apr

• On the date a quiz is given, a die will be thrown by a student in the class.
• Books and notes are put away.
• A question very similar to the chosen published question will be written on the board.
• You have 5 minutes to answer the question.
The questions are intended to be straightforward. If you keep up with the material in the class, almost no preparation may be necessary. The Collaboration Policy allows you to study in groups for the quizzes, but you are on your own when you take the quiz.

You will fare better on the quiz if you try working the problems before looking at the solutions. If you don't understand the question or its answer, please get help.

```import cs101.terminal.*;
public class bsearch {

int nums[];
public bsearch() {
nums = new int[100];
}

public int find(int n) {

int lo = 0;
int hi = nums.length-1;

while (lo < hi) {
int mid = (lo + hi)/2;
if (n <  nums[mid])  hi = mid - 1;
if (n >  nums[mid])  lo = mid + 1;
if (n == nums[mid])  lo = hi = mid;
}

if (lo == hi && nums[lo] == n) return(lo);
else return(-1);
}

public static void main(String[] args) { selfTest(); }
public static void selfTest() {
bsearch b = new bsearch();
for (int i=0; i < 100; ++i) {
b.nums[i] = 2*i;
}
for (int i=0; i < 100; i=i+12) {
Terminal.println("Find of " + (2*i) + " is " + b.find(2*i));
}
Terminal.println("Find of " + 3       + " is " + b.find(3));
}
}

```
1. Describe the range of values that can be returned by `find`.
2. In `find`, there are three `if` statements in the `while` loop. Argue that exactly one of them executes per iteration.
3. What is the loop termination condition?
4. What is the loop invariant that allows us to conclude that the `while` loop computes what is necessary?
5. Rewrite the bsearch class so that it uses the `Integer` class instead of primitive int.
6. What happens to the loop in `find` if its predicate is changed from ` lo < hi` to ` lo <= hi`?

[ solution ]