in C++ This is part of a series of functions that take in input from a file of 1
ID: 3813100 • Letter: I
Question
in C++
This is part of a series of functions that take in input from a file of 150 random non repeating numbers. Takes 10 numbers that the user enters, 5 of those numbers are in the list of random numbers and 5 are not. Then it displays an output of how many compares it took to find the number in the file (or not in the file).
Sp in this case load from a file, random and not duplicated numbers, this time sort in ascending order by using the insertion sort – sort the array from part 1 ( Call "any array", I can make the changes to call the right one) Then utilize a binary search method to search for each of the same 10 values (5 in list, 5 not). The program must return the number of compares it took to find (or NOT find) each number in the list.
The output would look like this:
Enter number: 5
Number found in position 17 and it took 8 compares to find it
Enter a number: 9
Number not found and it took 140 compares to find it
Explanation / Answer
#include <iostream>
#include <conio.h>
#include<fstream>
#define size 150
#define size1 10
using namespace std;
static int count;
int binarySearch(int *arr, int l, int r, int x)
{
count++;
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x) return mid;
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
int main()
{
ifstream in;
in.open("file.txt");
if(in==NULL)
{
cout<<"file not found";
return 0;
}
int i=0;
int a[size];
while(!in.eof())
{
in>>a[i];
i++;
}
int j,k,temp;
for (i = 1;i<size;i++)
{
for (j = i; j >= 1; j--)
{
if (a[j] < a[j-1])
{
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
else
break;
}
}
int b[size1];
cout<<"Enters 10 numbers: ";
for(int i=0;i<size1;i++)
cin>>b[i];
for(int i=0;i<size1;i++)
{ count=0;
int bb=binarySearch(a,0,size-1,b[i]);
if(bb==-1)
{
cout<<" Not Found and took "<<count<<" compares";
}
else
cout<<" Found and took "<<count<<" compares and found at the index position "<<bb;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.