Write a Java program to search two arrays of the same 1000 random integers in or
ID: 3831228 • Letter: W
Question
Write a Java program to search two arrays of the same 1000 random integers in order to test the efficiency of sequential and binary searches.
You will use the P10Class here:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class P10Class
{
public static int SEQ_NUM;
public static int BIN_NUM;
public static int seq_search(int[] data, int key)
{
boolean found = false;
int i = 0;
SEQ_NUM = 0;
while ( !found && (i < data.length) )
{
if ( data[i] == key )
found = true;
else
i++;
SEQ_NUM++;
}
if ( found )
return i;
else
return -1;
}
public static int bin_search(int[] data, int key)
{
boolean found = false;
int midpoint = 0, first = 0, last;
BIN_NUM = 0;
last = data.length - 1;
while ( ( first <= last ) && !found )
{
midpoint = (first + last) / 2;
if ( data[midpoint] == key )
found = true;
else if ( data[midpoint] > key )
last = midpoint - 1;
else
first = midpoint + 1;
BIN_NUM++;
}
if ( found )
return midpoint;
else
return -1;
}
}
This class is designed to test the efficiency of the two search models.
You will simultaneously populate both arrays with the same random numbers. This will guarantee that both arrays have the exact same content. Sort only ONE array using Arrays.sort(). This sorted array will be used with the bin_search() method and the unsorted array will be used with seq_search().
Write code to read integers from System.in until EOF. With each integer search each array using seq_search() and bin_search(). Report the number of elements examined for each search method, whether or not the item was found and where in the array you found it.
The number of array elements examined is stored in static instance variables. These variables for sequential and binary search are SEQ_NUM and BIN_NUM respectively. The appropriate variable is set when the corresponding search method is called.
Your output should resemble the following:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class P10Class
{
public static int SEQ_NUM;
public static int BIN_NUM;
public static int seq_search(int[] data, int key)
{
boolean found = false;
int i = 0;
SEQ_NUM = 0;
while ( !found && (i < data.length) )
{
if ( data[i] == key )
found = true;
else
i++;
SEQ_NUM++;
}
if ( found )
return i;
else
return -1;
}
public static int bin_search(int[] data, int key)
{
boolean found = false;
int midpoint = 0, first = 0, last;
BIN_NUM = 0;
last = data.length - 1;
while ( ( first <= last ) && !found )
{
midpoint = (first + last) / 2;
if ( data[midpoint] == key )
found = true;
else if ( data[midpoint] > key )
last = midpoint - 1;
else
first = midpoint + 1;
BIN_NUM++;
}
if ( found )
return midpoint;
else
return -1;
}
}
Explanation / Answer
I think the problem is deeper. I just wrote a program that JUST generates 2 identical arrays and then sorts one, and leaves the other one unsorted, and outputs the 2 arrays. By the end, the sorted array is mostly zeros, but the unsorted array is filled with numbers. This is 100% based on the part of my code above that generates the arrays, just made a bit smaller so the output is more readable. Run this code and see for yourself. So this is why one finds it and the other doesn't. Because both arrays aren't the same.
import java.util.*;
public class p10test
{
// keyboard object
static Scanner kb = new Scanner(System.in);
//MAIN METHOD
public static void main(String []args)
{
//Instance vairables
int[] bArray = new int[15];//Oh yeah
int[] sArray = new int[15];//arrays
int num = 0;
int integer = 0;
//intialize bArray to random numbers
for (num = 0; num < bArray.length; num++)
{
int randNumber = (int) (Math.random() * 15 + 1);
//assigns random number to our arrays
bArray[num] = randNumber;
sArray[num] = randNumber;
Arrays.sort(bArray);
printArray(sArray);
printArray(bArray);
}
}
public static void printArray(int[] a)
{
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
System.out.println();
System.out.println();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.