CS101 Quiz 10: Solutions

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.
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.
The loop terminates when lo >= hi.
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.

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));
   }
}

The loop will not terminate if n occurs in nums. Once found, lo=hi in perpetutity.