Lab-1: Comparison/Steps in Linear Search Vs Binary Search (2 marks):
Compare number of comparisons/steps taken by linear search and binary search in a sorted array to search an element. C file is given below. Put your java code after that.
· Take an array of size 1000
· Take 1000 integers as input in the array as sorted. Take A[i] = 2*i. It will make the array sorted
· Take an integer as input as a search value “key”
· Search the “key” in the array linearly and count the number of comparisons taken by the linear search
· Search the “key” again in the array by binary search and count the number of comparisons taken by the binary search
· Run the above two searching again and again for 10 times for 10 different keys given as follows and record the number of comparisons taken by linear search and binary search in the following table
Key
|
0
|
1998
|
2000
|
1000
|
502
|
122
|
1498
|
498
|
4
|
8
|
Number of comparisons taken by Linear search
|
|
|
|
|
|
|
|
|
|
|
Number of comparisons taken by Binary search
|
|
|
|
|
|
|
|
|
|
|
C File:
#include
#define ARRAY_SIZE 1000 // Size of the array
int key;
int A[ARRAY_SIZE]; // one dimensional array of size ARRAY_SIZE
int count_linear_search; // counter for number of comparison in linear search
int count_binary_search; // counter for number of comparison for binary search
void take_input_A(void)
{
int i;
for(i=0; i<ARRAY_SIZE; i++)
{
A[i] = 2*i; // this entry will make A sorted (0, 2, 4, 6, ..., 1998)
}
}
void search_A_linear(void) // search the array linearly from 0 to ARRAY_SIZE - 1
{
int i;
count_linear_search = 0; // count the number of comparison for linear search. Start from 0
for(i=0; i<ARRAY_SIZE; i++) // go gradually from 0 to ARRAY_SIZE-1
{
count_linear_search++; // count the number of comparison for linear search
if(A[i] >= key)
break; // if found or bigger, then get out of the loop
}
}
void search_A_binary(void) // search the array by binary search, as the array is sorted
{
int i, mid, first, last;
first = 0;
last = ARRAY_SIZE-1;
count_binary_search = 0; // count the number of comparison for binary search. Start from 0
while((first<=last))) // Array size is 1 or more, so binary search can be applied. Otherwise terminate
{
count_binary_search++; // count the number of comparison for binary search
mid = (last+first)/2; // find the middle position
if(key == A[mid]) // check if the key is in middle position
return; // if found, then return, no need to proceed any more
if(key > A[mid]) // if not found, then see if the key is bigger than the middle position
first = mid+1; // if bigger, then key can be available in the right side (not left side).
// So, make the array as left half by taking the firt as middle+1, last remains same
else
last = mid-1; // else, key can be in the left side (not right side).
// So, make the array left half by taking last as middle-1, first remains same
}
}
void main(void)
{
int i;
take_input_A(); // call the function to take sorted input in array A
printf("\nEnter a value to search: "); // take the key as input from the user
scanf("%d", &key);
search_A_linear(); // do linear search
search_A_binary(); // do binary search
printf("\nNumber of comparison for linear search: %d, binary search: %d\n", count_linear_search, count_binary_search);
// print how many comparisons are needed for linear search and binary search
}
Key
0
1998
2000
1000
502
122
1498
498
4
8
Number of comparisons taken by Linear search
1
1000
1000
501
252
62
750
250
3
5
Number of comparisons taken by Binary search
9
10
10
9
10
4
2
2
8
9
java file:
need an explanation for this answer? contact us directly to get an explanation for this answer