CS101 Quiz 10: Solutions

  1. find can return values in the range -1 to nums.length-1, inclusively. The value -1 indicates that the parameter to find was not found in nums.
  2. The predicates of the if statements are disjoint: in comparing n and nums[mid], one must be less than, equal to, or greater than the other.
  3. The loop terminates when lo >= hi.
  4. The loop invariant is that if n exists in nums, then it is found in the index range lo...hi. If the loop terminates with lo=hi, then we can check nums[lo] or nums[hi] and see if it matches n.
  5. import cs101.terminal.*;
    public class bsearchInt {
    
       Integer nums[];
       public bsearchInt() {
          nums = new Integer[100];
       }
          
          
       public int find(int n) {
    
          int lo = 0;
          int hi = nums.length-1;
    
          while (lo < hi) {
             int mid = (lo + hi);
             if (n <  nums[mid].intValue())  hi = mid - 1;
             if (n >  nums[mid].intValue())  lo = mid + 1;
             if (n == nums[mid].intValue())  lo = hi = mid;
          }
    
          if (lo == hi && nums[lo].intValue() == n) return(lo);
          else return(-1);
       }
    
       public static void main(String[] args) { selfTest(); }
       public static void selfTest() {
          bsearchInt b = new bsearchInt();
          for (int i=0; i < 100; ++i) {
             b.nums[i] = new Integer(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));
       }
    }
    
    
  6. The loop will not terminate if n occurs in nums. Once found, lo=hi in perpetutity.