int middle, first_index = 0, last_index = size -1,pos = -1; bool found = false;
ID: 3680305 • Letter: I
Question
int middle, first_index = 0, last_index = size -1,pos = -1;
bool found = false;
int comparisons = 0;
while(!found && first_index <= last_index)
{
middle = (first_index + last_index)/2;
if( x[middle]== val)
{
found = true; pos = middle;
comparisons++;
}
else if(x[middle] > val)
{last_index = middle -1;
comparisons++;
}
else
{
first_index = middle + 1;
comparisons++;
}
}
cout<<"No of Comparisons in binary search"<<comparisons<<endl;
return pos;
}
int linearSearch(int x[], int size, int value)
{ bool found = false;
int index = 0, pos = -1; int comparisons = 0;
Explanation / Answer
Binary search and Linear search code:
#include <iostream>
using namespace std;
int a[50];
int linearSearch(int x[], int arrLength, int item)
{
int i,n;
int value=0;
int index = 0;
int comparisons = 0;
for(i=0;i<arrLength;i++)
a[i]=x[i];
for(i=1;i<=n;i++) //Array Elements Comparsion with Item
{
if(a[i]==item)
{
value=a[i];
cout<<" Data is Found at Location : "<< i+1 << endl;
index=1;
break;
}
}
if(index==0)
{
cout<<"Data is Not Found";
}
return value;
}
int comparision()
{
int middle, first_index, last_index,pos = -1;
int x[50],arrSize;
int i,j,k;
int comparisons = 0;
bool found = false;
int val;
cout << "Enter the size of the array " ;
cin >> arrSize;
cout << "enter the elements in SORTED order" << endl;
for(i=0;i<arrSize;i++)
cin >> x[i];
cout << "enter key to be searched :";
cin>>val;
first_index=0,last_index=arrSize-1;
while(!found && first_index <= last_index)
{
middle = (first_index + last_index)/2;
if( x[middle]== val)
{
found = true; pos = middle;
comparisons++;
}
else if(x[middle] > val)
{last_index = middle -1;
comparisons++;
}
else
{
first_index = middle + 1;
comparisons++;
}
}
cout<<"No of Comparisons in binary search = "<<comparisons<<endl;
cout << "values is = "<< linearSearch(x,arrSize,val);
return pos;
}
int main()
{
comparision();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.