Question

Java: Write an application that has an array of at least 20 integers. It should call a method that uses the sequential search algorithm to locate one of the values. The method should keep a count of the number of comparisons it makes until it finds the value. Then the program should call another method that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen.

a. Create an array of 20 random integers.

b. Use the Bubble Sort Algorithm to sort this array in an ascending order.

c. Make a copy of this sorted array for use in the Binary Search method, using the array copy method called CopyArrayExample.java.

e. Print out the array before starting the search so that you will know which integer you want the two search methods to search for.

f. Run the Sequential Search algorithm and report the number of comparisons.

g. Run the Binary Search algorithm and report the number of comparisons.

CopyArrayExample.java:

public class CopyArrayExample {
   public static void main(String args[]){
       int a[]={10,20,30,40,50};
       int b[]=new int[a.length];
      
       //copying one array to another
       for(int i=0;i<a.length;++i){
           b[i]=a[i];
       }
      
       //printing array
       for(int i=0;i<b.length;++i){
           System.out.print(b[i]+" ");
       }
   }
}

Answer 1

import java.util.Random;
import java.util.Scanner;

public class CopyArrayExample {
   // sorting they array in ascending order using bubble sort
   public static void bubbleSort(int array[]) {

       int i, j, temp;
       int n = array.length;

       for (i = 0; i < n - 1; ++i) {

           for (j = 0; j < n - 1 - i; ++j) {

               if (array[j] > array[j + 1]) {

                   temp = array[j + 1];

                   array[j + 1] = array[j];

                   array[j] = temp;
               }

           }

       }
   }

   // performs binary search on the array and returns the number of
   // comparisions
   public static int binarySearch(int arr[], int l, int r, int x, int comp) {

       if (r >= l) {
           comp++;
           int mid = l + (r - l) / 2;
           if (arr[mid] == x) {
               return comp;
           }
           if (arr[mid] < x)
               return binarySearch(arr, mid + 1, r, x, comp);

           return binarySearch(arr, l, mid - 1, x, comp);
       }
       return comp;
   }

   public static void main(String args[]) {
       int a[] = new int[20];
       int b[] = new int[20];
       Random r = new Random();
       // copying one array to another
       for (int i = 0; i < a.length; ++i) {
           a[i] = r.nextInt(1000);
           // copying values into array
           b[i] = a[i];
       }
       bubbleSort(a);
       // printing array
       for (int i = 0; i < a.length; ++i) {
           System.out.print(a[i] + " ");
       }
       Scanner sc = new Scanner(System.in);
       // reading element to search in the array
       System.out.println("\nEnter element to search: ");
       int ele = sc.nextInt();
       // calling binary and linear search
       System.out.println(binarySearch(a, 0, a.length, ele, 0) + " comparisions required to find " + ele
               + " using binary search");
       System.out.println(linearSearch(b, ele) + " comparisions required to find " + ele + " using binary search");

   }

   // performs linear search on the array and returns number of comparisons
   // required
   private static int linearSearch(int[] aA, int aEle) {
       for (int i = 0; i < aA.length; i++) {
           if (aA[i] == aEle)
               return i + 1;
       }
       return -1;
   }
}