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.

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?