## CS 101 (Fall 2000) Quiz 10: Arrays and Binary Search

Quiz Posted
(Thursdays)
Given in class
(Thursdays)
9 Nov 16 Nov

### Information about quizzes:

• 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 terminal.*;
public class bsearch {

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

public int find(int targ) {
return bshelper(nums, 0, nums.length-1, targ);
}

public int bshelper(int[] nums, int lo, int hi, int targ) {

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

if (nums[lo] == targ) 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 ]

Last modified 19:23:26 CDT 06 April 1999 by Ron K. Cytron