Problem Statement Write a program that prompts the user to input two integers n
ID: 3743883 • Letter: P
Question
Problem Statement
Write a program that prompts the user to input two integers n and m, each should be between 1 and 20. Your program should use a method makeArray(...) which generates a list of random numbers between 0 and 99 and stores the first n values in one array of size (n-1) and the second set of m values in another array (m-1). Both arrays will be sorted using the method insertionSort(…). The contents of the two arrays will be displayed back, to the user, before and after each array is sorted using another method displayArray(…).
Then you will use another method mergeArrays(…) to merge all the elements from the previously created two arrays, into another array of size (n+m-1). The new 3rd array can be sorted inside the method as it gets merged, or using the method insertionSort(…). The contents of the new array will be displayed back, to the user, before and after it is sorted using method displayArray(…).
The user is then prompted one more time to enter an integer key. Your program should then use another method binarySearch(…) which will search each of the 3 arrays for the key the user supplied. If the key is found, your program will display the index / position of where in the array the key is located and which of the arrays contain this number (1st, 2nd, or 3rd) array. Otherwise, if the user supplied a key that is not found in any of the arrays, then display a message indicating the key was not found anywhere in any of the arrays. A sample output is below,
Hint: You should be able to upgrade and re-use most of what you did in other assignments, or find sample code in the textbook for initializing, insert-sorting, displaying arrays, generating random numbers, and binary search. Explain how everything works step by step.
Explanation / Answer
Here is the debugged code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// BinarySearch.java
import java.util.Scanner;
public class BinarySearch {
// scanner to read user input
static Scanner scanner = new Scanner(System.in);
// method to generate an array of size n, fill with random numbers
// return the generated array
static int[] makeArray(int n) {
int array[] = new int[n];
for (int i = 0; i < array.length; i++) {
// filling with random numbers between 0 and 99
array[i] = (int) (Math.random() * 100);
}
return array;
}
// method to display an array
static void displayArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.println("Index " + i + " : " + array[i]);
}
}
// method to sort the array in parameter using insertion sort
static void insertionSort(int[] array) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
}
}
// method to merge two arrays, sort and return it
static int[] mergeArrays(int[] array1, int[] array2) {
// creating array capable of storing all elements in array1 and array2
int array[] = new int[array1.length + array2.length];
int index = 0;
// adding array1 elements
for (int i = 0; i < array1.length; i++) {
array[index] = array1[i];
index++;
}
// adding array2 elements
for (int i = 0; i < array2.length; i++) {
array[index] = array2[i];
index++;
}
// sorting before returning
insertionSort(array);
return array;
}
// method to perform binary search in an array, return the index
// (-1 if not found)
static int binarySearch(int key, int array[]) {
int first = 0, last = array.length - 1;
int mid = (first + last) / 2;
while (first <= last) {
if (array[mid] < key) {
first = mid + 1;
} else if (array[mid] == key) {
return mid;
} else {
last = mid - 1;
}
mid = (first + last) / 2;
}
return -1;
}
public static void main(String[] args) {
System.out
.print("For array#1, how many numbers (max 20) would you like to generate? : ");
// getting n
int n = scanner.nextInt();
if (n < 1 || n > 20) {
// exiting the program if value given is outside the range
System.exit(0);
}
//making array
int array1[] = makeArray(n);
System.out.println("Array of " + n + " random numbers generated");
//displaying array
displayArray(array1);
//sorting array
insertionSort(array1);
System.out.println("Array of " + n + " random numbers sorted");
//displaying sorted array
displayArray(array1);
//similarly building up second array
System.out
.print("For array#2, how many numbers (max 20) would you like to generate? : ");
int m = scanner.nextInt();
if (m < 1 || m > 20) {
System.exit(0);
}
int array2[] = makeArray(m);
System.out.println("Array of " + m + " random numbers generated");
displayArray(array2);
insertionSort(array2);
System.out.println("Array of " + m + " random numbers sorted");
displayArray(array2);
//merging array1 and array2
int array3[] = mergeArrays(array1, array2);
System.out.println("Array of " + array3.length
+ " merged numbers sorted.");
displayArray(array3);
System.out.print("Now, type the integer you want to search: ");
//getting key value to search
int key = scanner.nextInt();
//searching in array1
int index = binarySearch(key, array1);
if (index != -1) {
System.out.println("Key match found in array#1 at index: " + index);
} else {
System.out.println("Key not found in array#1");
}
//searching in array2
index = binarySearch(key, array2);
if (index != -1) {
System.out.println("Key match found in array#2 at index: " + index);
} else {
System.out.println("Key not found in array#2");
}
//searching in array3
index = binarySearch(key, array3);
if (index != -1) {
System.out.println("Key match found in array#3 at index: " + index);
} else {
System.out.println("Key not found in array#3");
}
}
}
/*OUTPUT*/
For array#1, how many numbers (max 20) would you like to generate? : 3
Array of 3 random numbers generated
Index 0 : 92
Index 1 : 26
Index 2 : 98
Array of 3 random numbers sorted
Index 0 : 26
Index 1 : 92
Index 2 : 98
For array#2, how many numbers (max 20) would you like to generate? : 5
Array of 5 random numbers generated
Index 0 : 79
Index 1 : 72
Index 2 : 37
Index 3 : 66
Index 4 : 1
Array of 5 random numbers sorted
Index 0 : 1
Index 1 : 37
Index 2 : 66
Index 3 : 72
Index 4 : 79
Array of 8 merged numbers sorted.
Index 0 : 1
Index 1 : 26
Index 2 : 37
Index 3 : 66
Index 4 : 72
Index 5 : 79
Index 6 : 92
Index 7 : 98
Now, type the integer you want to search: 72
Key not found in array#1
Key match found in array#2 at index: 3
Key match found in array#3 at index: 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.