Homework SourseJava Help Using binary search write a BinarySearchEvaluator
Java Help:
Using binary search, write a BinarySearchEvaluator class, with the following specifications:
• Member variables array and size, where array is an array of integers arranged in sorted order (smallest to largest), and size is the the size of the array
• Member variable numCalls, initialized to 0, which keeps track of the number of times the binarySearch method is called
• Member methods:
• constructor: takes argument for size, creates array to hold the specified number of values; populates array with random increasing values between 1 and size * 10
• binarySearch: finds the value specified in its first argument and increments numCalls each time it is called
• reset: sets numCalls back to 0 and repopulates array
• getNum: returns value of numCalls
• main method to test the others; should run algorithm several times, using randomly generated values to search for, and reports:
• whether or not search for particular value was successful
• value of numCalls at the end of each search cycle
Solution
PROGRAM CODE:
package binarysearch;
import java.util.Random;
public class BinarySearchEvaluator {
int size;
int array[];
int numCalls;
public BinarySearchEvaluator( int size) {
Random random = new Random();
this.size = size;
this.numCalls = 0;
array = new int[size];
array[0] = 1;
int randomValue;
for(int i=1; i<size-1; i++)
{
randomValue = random.nextInt(i*10);
while(randomValue<array[i-1])
randomValue = random.nextInt(i*10);
array[i] = randomValue;
}
array[size-1] = size*10;
}
public int binarySearch (int n, int first, int extent) {
int mid = first + ((extent-first)/2);
numCalls++;
/* added parens, in case anyone (like me :P) forgets order of operations */
if (extent == 0) {
return -1;
}
else if (n > array[extent-1]) {
/* I added this block to handle values larger than the max value in the array;
* numbers < the lowest value in the array are already handled just fine */
return -1;
}
else if (n < array[0]) {
// if n is lower than the lowest in the array, shortcut multiple recursive
// calls and return -1
return -1;
}
else {
if (array[mid] < n) {
return binarySearch(n, mid+1, extent);
/* the return statement
* here is important, otherwise we will return the wrong instance
* of \'mid\' (due to recursion) */
}
else if (array[mid] > n) {
return binarySearch(n, first, mid);
/* the return statement here
* is important, otherwise we will return the wrong instance of
* \'mid\' (due to recursion) */
}
else {
return mid;
}
}
}
public void reset()
{
BinarySearchEvaluator eval = new BinarySearchEvaluator(size);
this.numCalls = eval.numCalls;
this.array = eval.array;
eval = null;
}
public int getNum()
{
return numCalls;
}
public static void main(String args[])
{
BinarySearchEvaluator evaluator = null;
Random randomGen = new Random();
for(int i=0; i<15; i++)
{
int random = randomGen.nextInt(i+10) + 5;
evaluator= new BinarySearchEvaluator(random);
int searchInt = randomGen.nextInt(random) + 1;
System.out.print(\"Searching for \" + (searchInt) + \": \");
int result = evaluator.binarySearch(searchInt, 1, random);
if(result == -1)
System.out.println(\"Number not found\");
else System.out.println(\"Number found at \" + result);
System.out.println(\"Total Number of calls: \" + evaluator.getNum() + \"\ \");
}
}
}
OUTPUT:
Searching for 2: Number not found
Total Number of calls: 4
Searching for 8: Number found at 1
Total Number of calls: 4
Searching for 5: Number not found
Total Number of calls: 4
Searching for 9: Number not found
Total Number of calls: 4
Searching for 4: Number not found
Total Number of calls: 4
Searching for 5: Number not found
Total Number of calls: 4
Searching for 3: Number not found
Total Number of calls: 4
Searching for 4: Number not found
Total Number of calls: 3
Searching for 2: Number not found
Total Number of calls: 6
Searching for 13: Number not found
Total Number of calls: 5
Searching for 22: Number not found
Total Number of calls: 4
Searching for 2: Number found at 1
Total Number of calls: 4
Searching for 7: Number not found
Total Number of calls: 3
Searching for 14: Number not found
Total Number of calls: 4
Searching for 7: Number found at 2
Total Number of calls: 3
