Quiz | Posted (Thursdays) |
Given in class (Thursdays) |
||
---|---|---|---|---|
6 | Apr | 13 | 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 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)); } }
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
?