Compare the performance of Linear and Binary Search algorithms. You are given a

Question

Compare the performance of Linear and Binary Search algorithms.
You are given a data file (SearchData.txt) containing:
Line #1: Number of values in the data that is being searched (N)
Line #2: Number of values that are searched in data (K)
Line #3: Data values (N of them)
Line #4: Search values (K of them)
Your program should output the following to an output file:
Line#1: Average time to perform all searches using Linear Search (i.e. Total time/K)
Line#2: Average time to perform all searches using Binary Search
Line #3: The locations in the array where the search values are found (separated by spaces).
Output -1 if a value is not found. Hint: this should be identical for both linear and binary
searches.
If the data file contains:
5
6
10 20 30 40 50
40 10 35 15 40 20
Here is an example for Line#3 in the output file:
3 0 -1 -1 3 1
You are not allowed to use JAPA API Arrays, Collection or Collections classes (ArrayLists etc). Use built-in
arrays for storing data and System class for measuring time.
Here is the outline of the process for the above comparison:
1. Read Data from the provided files and store it in arrays - one array for the data that is being searched
and the other for the search values
3. Measure time for performing K linear searches. Write this to the output file (line #1)
4. Measure time for performing K binary searches. Write this to the output file (line #2)
5. Perform K binary searches and write the results to output file (line #3)

Explanation / Answer

#include <iostream>
#include <cstdio>
#include <time.h>

using namespace std;
int arr[1000], test[100];
int n, k;
int binary_search( int val , int low, int high)
{
int ans ;
if ( high < low ) ans = -1;
else
{
int mid = (low+high) / 2;
if( arr[mid] == val)
ans = mid;
else
if (arr[mid] > val)
ans = binary_search( val, low, mid-1);
else
ans = binary_search( val, mid+1, high);
}
return ans;
}
int linear_search( int val )
{
int ans = -1;
for( int i = 0; i < n; i++)
if( arr[ i ] == val )
{
ans = i;
break;
}
return ans;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin >> n >> k;
for(int i = 0; i<n ; i++)
cin >> arr[i] ;
for(int i = 0; i<k ; i++)
cin >> test[i] ;
  
cout << "LINEAR SEARCH" << endl;
clock_t tStart = clock();
for(int i = 0; i<k ; i++)
cout << linear_search( test[i] ) << " ";
cout << endl;
printf("Time taken: %.2fs ", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  
cout << "BINARY SEARCH" << endl;
tStart = clock();
for(int i = 0; i<k ; i++)
cout<< binary_search( test[i], 0, n-1 ) << " ";
cout << endl;
printf("Time taken: %.2fs ", (double)(clock() - tStart)/CLOCKS_PER_SEC);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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