Quiz | Posted (Wednesdays) |
Given in class (Wednesdays) |
||
---|---|---|---|---|
7 | Apr | 14 | Apr |
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)); } }
find
.
find
, there are three if
statements in
the while
loop. Argue that exactly one of them executes per
iteration.
while
loop computes what is necessary?
Integer
class instead of primitive int.
find
if its predicate is
changed from lo < hi
to lo <= hi
?