CISS-110 Project 10

CISS-110 Project 10

Write a Java program to search two arrays of the same 1000 random integers in each to test the efficiency of sequential and binary searches.

---

Learning outcomes

• Implementing user-defined classes.
• Working with sorts.
• Working with search algorithms.
• Understanding Big-O notation and how it applies to algorithms.
• Confirmation program produces desired results.

---

You will use the P10Search here:

public class P10Search {
  public static int SEQ_NUM;
  public static int BIN_NUM;
  
  public static int seqSearch(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++;
    }
    
    return found ? i : -1;
  }
  
  public static int binSearch(int[] data, int key) {
    boolean found = false;
    int midpoint = 0, first = 0, last;
    
    BIN_NUM = 0;
    last = data.length - 1;
    
    while ( !found && ( first <= last ) ) {
      midpoint = (first + last) / 2;
      if ( data[midpoint] == key )
        found = true;
      else if ( data[midpoint] > key )
        last = midpoint - 1;
      else
        first = midpoint + 1;
      
      BIN_NUM++;
    }
    
    return found ? midpoint : -1;
  }
}

This class is designed to test the efficiency of the two search models. Your Project10_lastname.java program should be written such that it extends P10Search.

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 binSearch() method, and the unsorted array will be used with seqSearch().

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:

1000 random numbers from 0 to 999 have been generated 

Enter an integer to search the arrays (EOF to stop): 467
sequential search found the value  467 in element 500 with   501 items scanned. 
binary     search found the value  467 in element 461 with     9 items scanned. 

Enter an integer to search the arrays (EOF to stop): 999
sequential search found the value  999 in element 475 with   476 items scanned. 
binary     search found the value  999 in element 998 with     9 items scanned. 

Enter an integer to search the arrays (EOF to stop): 34
sequential search did not find the value with  1000 items scanned. 
binary     search did not find the value with    10 items scanned. 

Enter an integer to search the arrays (EOF to stop): 145
sequential search found the value  145 in element 499 with   500 items scanned. 
binary     search found the value  145 in element 141 with     9 items scanned.

Enter an integer to search the arrays (EOF to stop): CTRL-D

---

Submit the project to the Learning Management System as Project10_lastname.java.