Linear Search Vs Binary Search Objective: Implement both linear search and binar

Question

Linear Search Vs Binary Search Objective: 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 mennd pied wh andan values from 0-999 A value to be searched in the said array is randomly selected from the range 0-999 o 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 o Search the array next o Return whether or not the value was found in the array Implement both searches as a method o However instead of returning whether or not it found the number it should return the number of checks o Whether the value is or is not found can be printed in the method Binary search is fairly simple to create using recursion o Do not count the out of bounds or stopping index as a check

Explanation / Answer

JAVA PROGRAM:

import java.util.Random;

public class LinearBinary {

public static void main(String[] args) {

// TODO Auto-generated method stub

int list[]=new int[1000];

for(int i=0;i<1000;i++)

list[i]=i;

int maximum=1000;

int minimum=1;

int liCount=0,biCount=0;

int liTotalChecks=0,biTotalChecks=0;

System.out.println("Welcome to the Search Tester. We are going to see which");

System.out.println("algorithem performs the best out of 20 tests");

for(int i=0;i<19;i++)

{

Random rn = new Random();

int range = maximum - minimum + 1;

int randomNum = rn.nextInt(range) + minimum;

System.out.println("Searching using linear search Found!");

System.out.println("Searching using binary search Found!");

liCount=linearSearch(list,randomNum);

System.out.println("Linear Checks : "+liCount);

biCount=binarySearch(list,randomNum);

System.out.println("Binary Checks : "+biCount);

liTotalChecks+= liCount;

biTotalChecks+=biCount;

}

System.out.println("The average Number of Checks for 20 were : ");

System.out.println("Linear Search : "+liTotalChecks/20);

System.out.println("Binary Search : "+biTotalChecks/20);

}

static int binarySearch(int arr[], int x)

{

int l = 0, r = arr.length - 1,count=0;

while (l <= r)

{

count++;

int m = l + (r-l)/2;

// Check if x is present at mid

if (arr[m] == x)

break;

// If x greater, ignore left half

if (arr[m] < x)

l = m + 1;

// If x is smaller, ignore right half

else

r = m - 1;

}

// if we reach here, then element was not present

return count;

}

private static int linearSearch(int[] arr , int k)

{

int count=0;

for (int i = 0; i < 1000; i++)

{

count++;

if (arr[i] == k)

break;

}

return count;

}

}

OUTPUT:-

Welcome to the Search Tester. We are going to see which
algorithem performs the best out of 20 tests
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 805
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 543
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 590
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 398
Binary Checks : 7
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 828
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 319
Binary Checks : 7
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 450
Binary Checks : 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 260
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 640
Binary Checks : 6
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 438
Binary Checks : 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 877
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 991
Binary Checks : 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 620
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 180
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 105
Binary Checks : 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 910
Binary Checks : 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 822
Binary Checks : 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks : 754
Binary Checks : 10

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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