Quiz 4 Binary Search vs. Brute Force Search Algorithms for Finding a Local Minim
ID: 3724098 • Letter: Q
Question
Quiz 4 Binary Search vs. Brute Force Search Algorithms for Finding a Local Minimum in a Two- Dimensional Array In this project, you will implement the binary search-based (n) algorithm to determine the local minimum in an 'n'x 'n'two-dimensional array (as discussed in Module 2) and compare its run-time performance with that of a brute force O(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 mam is found. You should create random two-dimensional arrays (with numRows = numCols) with unique elements in the range... numRows numCols] for the following values of numRows (numCols) and determi the average execution time of the binary search and the brute force search algorithms by running 200 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,3 Plot the results with numRows in X-axis and the average execution times (in nanoseconds or milliseconds) of the binary search and the brute force search algorithms in the Y-axis (1 65 pts) Code for the binary search and the brute force search algorithms (2-15 pts) Excel plots of the numRows vs. average execution times of the two algorithms (3 - 20 pts) Your interpretation of the results. *use javáaExplanation / Answer
class Binary_Seearch{
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
private static void search(int[][] mat, int n, int x) {
long startTime = System.nanoTime();
int i = 0, j = n-1; //set indexes for top right
// element
while ( i < n && j >= 0 )
{
if ( mat[i][j] == x )
{
System.out.print("n Found at "+ i + " " + j);
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println(totalTime);
return;
}
if ( mat[i][j] > x )
j--;
else // if mat[i][j] < x
i++;
}
System.out.print("n Element not found");
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println(totalTime);
return; // if ( i==n || j== -1 )
}
class Linear_Seearch{
private static void search(int[][] mat, int n, int x) {
long startTime = System.nanoTime();
int i = 0, j = 0; //set indexes for top right
// element
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if ( mat[i][j] == x )
{
System.out.print("n Found at "+ i + " " + j);
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println(totalTime);
return;
}
}
}
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println(totalTime);
System.out.print("n Element not found");
return;
}
// driver program to test above function
public static void main(String[] args) {
int mat[][] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50} };
search(mat, 4, 29);
}
}
Thumbs up!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.