Problem Description In this project, you will load arrays of increasing size wit

Question

Problem Description
In this project, you will load arrays of increasing size with integers and search the array for a particular value. You
will count the operations performed in searching and plot these as a function of the size of the array.
You will use integers drawn from a random number generator (use java.util.Random in Java, or random() or
something equivalent if using C++), with values drawn from a range determined by the array size.
Run the linear search for array size N = 256, 512, 1024, 2048, 4096, 8192, 16384, 32768. Your empirical
test will do the following:
for each array size N {
initialization
load array with N random numbers in the range 0 to (N-1)
for each array search operation (performed M times){
// M is say 10% of the array size
generate search 'val', a random number in the range 0 to (N-1)
search for val , accumulate number o array comparisons
}
output N and accumulated number of comparisons
}
Implementation Details
Input: All input is generated using random numbers. No interactive input is permitted.
Output: The following guidelines must be strictly followed for full credit:
{ A single run of the application should produce all of the needed output.
{ Your application will output two columns of numbers, input size N and corrresponding number of
comparisons.
{ You will use the table generated in the previous step and generate a single graph that shows the
plot of N (horizontal axis) vs. number of comparisons(vertical axis). Use any plotting program but
generate an output in Jpeg, PDF, PNG or any format that is easily viewable. The graph will be
generated outside of the application.

Explanation / Answer

import java.util.*; public class LinearSearch { public int find(final int[] data, final int key) { for (int i = 0; i key) return -1; else if (data[i] == key) return i; } return -1; } public static void main(String[] args) { final int arr[] = new int[10]; System.out.println("Enter 10 numbers"); Scanner input = new Scanner(System.in); for (int i = 0; i = 0) && (n

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.