Implement the binary search-based (n) algorithm to determine the local minimum i
ID: 3804654 • Letter: I
Question
Implement the binary search-based (n) algorithm to determine the local minimum in an 'n' x 'n' two-dimensional array and compare its run-time performance with that of a brute force (n2 ) algorithm that searches for the local minimum element by element until one is found. Note that both the binary search and the brute force search algorithms should stop once a local minimum is found. You should create random two-dimensional arrays (with numRows = numCols) with unique elements in the range [1... numRows * numCols] for the following values of numRows (numCols) and determine the average execution time of the binary search and the brute force search algorithms by running 100 trials for each of the numRows (numCols) values. Determine the running times in nano seconds or milli seconds, as appropriate. numRows (numCols) values: 4, 6, 8, 10, 15, 20, 25, 30, 35, 40, 50, 75, 100, 150, 200, 250, 300, 350 Plot the results with numRows in X-axis and the average execution times of the binary search and the brute force search algorithms in the Y-axis.
Please do the programming in Java and be detailed (adding in comments to explain how your code works). Thank you!
Explanation / Answer
Answer:
public class Binarysearchapp {
public int binarySearch(int[] value, int input) {
int begin = 0;
int last = value.length - 1;
while (begin <= last) {
int between = (begin + last) / 2;
if (input == value[between]) {
return between;
}
if (input < value[between]) {
last = between - 1;
} else {
begin = between + 1;
}
}
return -1;
}
public static void main(String[] args) {
Binarysearchapp mbs = new Binarysearchapp();
int[] arr = { 4, 6, 8, 10, 15, 20, 25, 30, 35, 40, 50, 75, 100, 150, 200, 250, 300, 350};
System.out.println("input 14's position: "+mbs.binarySearch(arr, 10));
}
}