Question

1.You are to write a program name search.java that will do the following:

2.You are to create 3 arrays - prompt the user for a number that is greater than 100 that will serve as the size for the arrays (all 3 arrays will have the same user input size). Call them A, B & C.

3.Generate this amount of random numbers to fill these arrays – the random numbers must range from 1 to 99.

4.Write 1 sequential search voided function (method) name Seq_search() that accepts two parameters – 1 array and a target value to search for. Call this method 3 times (pass Array A as one of the paramters) à once with a target value of 1, next with a target value of 50 and next with a target value of 100. Each time you call this method, you must invoke a clock to see how long it takes to execute and print out the time with an appropriate message.

5.Write 1 binary search voided function (method) using Loop only, name Bin_search() that accepts two parameters – 1 array and a target value to search for. In the main program first sort array B and time it to see how long it took to sort. Now pass this sorted array as a parameter to this method calling it 3 times à once with a target value of 1, next with a target value of 50 and next with a target value of 100. Each time you call this method, you must invoke a clock to see how long it takes to execute and add the time it took to sort the array to this time and print out the time with an appropriate message.

6.Write 1 binary search voided function (method) that uses recursion only, name BinRe_search() that accepts two parameters – 1 array and a target value to search for. In the main program first sort array C and time it to see how long it took to sort. Now pass this sorted array as a parameter to this method calling it 3 times à once with a target value of 1, next with a target value of 50 and next with a target value of 100. Each time you call this method, you must invoke a clock to see how long it takes to execute and add the time it took to sort the array to this time and print out the time with an appropriate message.

7.After you get the time, give an analysis as to which you think is a better algorithm to use and under what circumstance it is better to be used.

Answer 1

Complete Program:

// File: search.java
import java.util.Random;
import java.util.Scanner;
public class search
{
public static int Seq_search(int[] arr, int target)
{
  for(int i = 0; i < arr.length; i++)
  {
   if(arr[i] == target)
    return i;
  }
  
  return -1;
}
  
public static void Sel_sort(int[] arr)
{
  for(int i = 0; i < arr.length - 1; i++)
  {
   int minPos = i;
   for(int j = i + 1; j < arr.length; j++)
   {
    if(arr[minPos] > arr[j])
    {
     minPos = j;
    }
   }

   if(i != minPos)
   {
    int temp = arr[i];
    arr[i] = arr[minPos];
    arr[minPos] = temp;
   }
  }
}

public static int Bin_search(int[] arr, int target)
{
  int first = 0;
  int last = arr.length - 1;

  while(first <= last)
  {
   int middle = (first + last) / 2;

   if(arr[middle] == target)
    return middle;
   
   if(arr[middle] < target)
    first = middle + 1;    
   else
    last = middle - 1;
  }

  return -1;
}

public static int BinRe_search(int[] arr, int target)
{
  return BinRe_search(arr, 0, arr.length - 1, target);
}
  
private static int BinRe_search(int[] arr, int first, int last, int target)
{
  if(first > last)
   return -1;
  
  int middle = (first + last) / 2;
  
  if(arr[middle] == target)
   return middle;
  
  if(arr[middle] < target)
   return BinRe_search(arr, middle + 1, last, target);
  else
   return BinRe_search(arr, first, middle - 1, target);
}

public static void main(String[] args)
{
  Scanner input = new Scanner(System.in);
  Random rand = new Random();
  
  System.out.print("Enter the size of the arrays: ");
  int size = input.nextInt();
  
  while(size <= 100)
  {
   System.out.print("Enter the size of the arrays > 100: ");
   size = input.nextInt();
  }
  
  int A[] = new int[size];
  int B[] = new int[size];
  int C[] = new int[size];
  
  for(int i = 0; i < size; i++)
  {
   int number = 1 + rand.nextInt(99);
   
   A[i] = number;
   B[i] = number;
   C[i] = number;
  }
  
  long before, after, elapsed;
  int idx1, idx50, idx100;
    
  // test for sequential search
  before = System.nanoTime();
  idx1 = Seq_search(A, 1);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx1 > -1)
   System.out.println("\n1 is found at the index " + idx1 + " in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("\n1 is not found in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
    
  before = System.nanoTime();
  idx50 = Seq_search(A, 50);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx50 > -1)
   System.out.println("50 is found at the index " + idx50 + " in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("50 is not found in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
  
  before = System.nanoTime();
  idx100 = Seq_search(A, 100);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx100 > -1)
   System.out.println("100 is found at the index " + idx100 + " in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("100 is not found in the array. Sequential Search has done in " + elapsed + " nanoseconds.");
    
  // test for binary search
  before = System.nanoTime();
  Sel_sort(B);
  after = System.nanoTime();
  elapsed = after - before;
  
  System.out.println("\nSorting has done in " + elapsed + " nanoseconds.");
  
  before = System.nanoTime();
  idx1 = Bin_search(B, 1);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx1 > -1)
   System.out.println("1 is found at the index " + idx1 + " in the array. Binary Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("1 is not found in the array. Binary Search has done in " + elapsed + " nanoseconds.");
    
  before = System.nanoTime();
  idx50 = Bin_search(B, 50);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx50 > -1)
   System.out.println("50 is found at the index " + idx50 + " in the array. Binary Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("50 is not found in the array. Binary Search has done in " + elapsed + " nanoseconds.");
  
  before = System.nanoTime();
  idx100 = Bin_search(B, 100);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx100 > -1)
   System.out.println("100 is found at the index " + idx100 + " in the array. Binary Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("100 is not found in the array. Binary Search has done in " + elapsed + " nanoseconds.");
    
  // test for recursive binary search
  before = System.nanoTime();
  Sel_sort(C);
  after = System.nanoTime();
  elapsed = after - before;
  
  System.out.println("\nSorting has done in " + elapsed + " nanoseconds.");
  
  before = System.nanoTime();
  idx1 = BinRe_search(C, 1);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx1 > -1)
   System.out.println("1 is found at the index " + idx1 + " in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("1 is not found in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
    
  before = System.nanoTime();
  idx50 = BinRe_search(C, 50);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx50 > -1)
   System.out.println("50 is found at the index " + idx50 + " in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("50 is not found in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
  
  before = System.nanoTime();
  idx100 = BinRe_search(C, 100);
  after = System.nanoTime();
  elapsed = after - before;
  
  if(idx100 > -1)
   System.out.println("100 is found at the index " + idx100 + " in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
  else
   System.out.println("100 is not found in the array. Recursive Binary Search has done in " + elapsed + " nanoseconds.");
}
}

Sample Output:

$5gMOYkbjjvQAAAABJRU5ErkJggg==$

From the Sample Output, Bin_search() method takes the least amount of time to search an elelemt in an array. So Bin_search() method is better than Seq_search() and BinRe_search() methods.