Question

Objective in JAVA (Please show output and have the avergae number of checks also.):

Implement both linear search and binary search, and see which one performs better given an array 1,000 randomly generated whole numbers (between 0-999), a number picked to search that array at random, and conducting these tests 20 times.  Each time the search is conducted the number of checks (IE number of times the loop is ran or the number of times the recursive method is called) needs to be counted and at the end the total number of checks should be averaged.

A few notes

Each algorithm (linear search and binary search) is ran 20 times

Each time a new sorted array of whole numbers is created and populated with random values from 0-999

A value to be searched in the said array is randomly selected from the range 0-999

Each algorithm must display if that number was successfully found

Each algorithm must display the number of checks it took to determine the above answer

It is advisable to create a method that returns the sorted array

Populate the array with random numbers

Search the array next

Return whether or not the value was found in the array

Implement both searches as a method

However instead of returning whether or not it found the number it should return the number of checks.

Whether the value is or is not found can be printed in the method

Binary search is fairly simple to create using recursion

Do not count the out of bounds or stopping index as a check

Example:

Welcome to the search tester.  We are going to see which algorithm performs the best out of 20 tests

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 753

Binary Checks: 8

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 834

Binary Checks: 10

Searching using linear search

Not Found

Searching using binary search

Not Found

Linear Checks: 1000

Binary Checks: 10

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 515

Binary Checks: 6

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 757

Binary Checks: 7

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 395

Binary Checks: 9

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 117

Binary Checks: 7

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 334

Binary Checks: 10

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 521

Binary Checks: 9

Searching using linear search

Not Found

Searching using binary search

Not Found

Linear Checks: 1000

Binary Checks: 10

Searching using linear search

Not Found

Searching using binary search

Not Found

Linear Checks: 1000

Binary Checks: 10

Searching using linear search

Not Found

Searching using binary search

Not Found

Linear Checks: 1000

Binary Checks: 10

Searching using linear search

Not Found

Searching using binary search

Not Found

Linear Checks: 1000

Binary Checks: 10

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 901

Binary Checks: 10

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 626

Binary Checks: 8

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 361

Binary Checks: 9

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 630

Binary Checks: 9

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 443

Binary Checks: 7

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 818

Binary Checks: 10

Searching using linear search

Found!

Searching using binary search

Found!

Linear Checks: 288

Binary Checks: 7

The average number of checks for 20 were:

Linear Search 664

Binary Search 8

Answer 1

import java.util.Arrays;
import java.util.Random;

public class Test{  
   public static int linearSearch(int arr[], int key){
       int iterations = 0;
       for(int i = 0; i < arr.length; i++){
           iterations++;
           if(arr[i] == key){
               System.out.println("Found!");
               return iterations;
           }
       }
       System.out.println("Not Found");
       return iterations;
   }  
   public static int binarySearch(int arr[], int key){
       int low = 0, high = arr.length - 1;
       int iterations = 0;
       while(high >= low){
           iterations++;
           int mid = (low + high) / 2;
           if(arr[mid] == key){
               System.out.println("Found!");
               return iterations;              
           }
           else if(arr[mid] > key){
               high = mid - 1;
           }
           else{
               low = mid + 1;
           }
       }
       System.out.println("Not Found");
       return iterations;
   }
   private static int[] generateRandomArray(){
       Random r = new Random();
       int arr[] = new int[1000];
       for(int i = 0; i < 1000; i++){
           arr[i] = r.nextInt(1000);
       }
       Arrays.sort(arr);
       return arr;
   }
   public static void main(String args[]){
       System.out.println("Welcome to the search tester. We are going to see which algorithm performs the best out of 20 tests");
       Random r = new Random();
       int avgLinearChecks = 0;
       int avgBinaryChecks = 0;
       for(int i = 1; i <= 20; i++){
           int arr[] = generateRandomArray();
           System.out.println("Searching using linear search");
           System.out.println("Searching using binary search");
           int keyToSearch = r.nextInt(1000);
           int linearSearchIterations = linearSearch(arr, keyToSearch);
           avgLinearChecks += linearSearchIterations;
           int binarySearchIterations = binarySearch(arr, keyToSearch);
           avgBinaryChecks += binarySearchIterations;
           System.out.println("Linear Checks: " + linearSearchIterations);
           System.out.println("Binary Checks: " + binarySearchIterations);
       }
       System.out.println("The average number of checks for 20 were:");
       avgLinearChecks /= 20;
       avgBinaryChecks /= 20;
       System.out.println("Linear Search " + avgLinearChecks);
       System.out.println("Binary Search " + avgBinaryChecks);
   }
}