The most common answer to the 10.2.8 Maximum Iterations Java Codehs answer is:
import java.util.*;
public class BinarySearchTest {
static int count;
public static void main(String[] args) {
// Use the helper code to generate arrays, calculate the max
// iterations, and then find the actual iterations for a randomly
// selected value.
Scanner input = new Scanner(System.in);
System.out.println("Array Size: 100");
System.out.println("Max iterations: " + binaryMax(100));
binaryRec(generateArrayOfLength(100), 2, 0, 99);
System.out.println("Actual iterations: " + count);
System.out.println();
count = 0;
System.out.println("Array Size: 1000");
System.out.println("Max iterations: " + binaryMax(1000));
binaryRec(generateArrayOfLength(1000), 2, 0, 999);
System.out.println("Actual iterations: " + count);
System.out.println();
count = 0;
System.out.println("Array Size: 10000");
System.out.println("Max iterations: " + binaryMax(10000));
binaryRec(generateArrayOfLength(10000), 2, 0, 9999);
System.out.println("Actual iterations: " + count);
System.out.println();
count = 0;
System.out.println("Array Size: 100000");
System.out.println("Max iterations: " + binaryMax(100000));
binaryRec(generateArrayOfLength(100000), 2, 0, 99999);
System.out.println("Actual iterations: " + count);
}
public static int binaryRec(int[] array, int target, int begin, int end) {
if (begin <= end)
{
int mid = (begin + end) / 2;
count ++;
// Base Case
if (target == array[mid]) {
return mid;
}
if (target < array[mid]) {
return binaryRec(array, target, begin, mid - 1);
}
if (target > array[mid]) {
return binaryRec(array, target, mid + 1, end);
}
}
return -1; //Alternate Base Case - not found
}
public static int[] generateArrayOfLength(int length)
{
int[] arr = new int[length];
for(int i = 0; i < length; i++)
{
arr[i] = (int)(Math.random() * 100);
}
Arrays.sort(arr);
return arr;
}
private static int binaryMax(int length) {
return (int) (Math.log(length) / Math.log(2)) + 1;
}
}This Java code implements a Binary Search Test, which includes methods for performing a binary search recursively (binaryRec), generating a sorted array of a given length (generateArrayOfLength), and calculating the maximum number of iterations required to perform a binary search on an array of a given size (binaryMax).
The program runs tests for arrays of different sizes (100, 1000, 10000, 100000) and prints the maximum iterations and actual iterations required to find a target value using binary search.
Let’s walk through the key parts of the code:
binaryRecMethod: Performs recursive binary search. It increments a global countercountto track the number of iterations (or recursive calls) made during the search process.generateArrayOfLengthMethod: Generates a sorted array of random integers of a specified length. It fills the array with random numbers and then sorts it.binaryMaxMethod: Calculates the maximum number of iterations needed to perform a binary search on an array of a specified size. This is based on the principle that the maximum number of steps in a binary search islog2(n) + 1, wherenis the array size.- Main Method: Runs the binary search test for arrays of sizes 100, 1000, 10000, and 100000. It first prints the array size and the calculated maximum iterations. Then it performs a recursive binary search on a target value (in this case, always
2) within a newly generated array and prints the required number of iterations.
The target value2is used consistently for simplicity, but since the arrays are randomly generated, the actual presence and position of2in each array can vary, affecting the actual iterations count.
It’s worth noting that the arrays are filled with random numbers and sorted, and the target for the binary search is set to 2. Given the randomness, the “Actual iterations” might vary or the target might not be present at all in some runs, which is a suitable demonstration of binary search behavior in various scenarios.
This Java code is well-structured for educational purposes. It illustrates how binary search works, how to implement it recursively, and how to assess its efficiency in terms of iterations.
