Question

In C++

Write a program to find the number of comparisons using binarySearch and the sequential search algorithm as follows:
Suppose list is an array of 1000 elements.
5.1 Use a random number generator to fill list.

Answer 1

#include <iostream>

using namespace std;

//function to find an element using sequential search
int sequentialSearch(int arr[], int size, int target)
{
int countNumCom = 0;
for(int i=0; i<size; i++)
{
countNumCom++;
if(arr[i] == target)
return i;
}
  
return countNumCom;
}

//binary search algorithm
int binarySearch(int arr[], int min, int max, int target)
{
//in every recursive call we are comparing the element three time
//compare one
if (max >= min)
{
//Compute guess as the average of max and min
int guess = (max+min)/2;

//compare two
if (arr[guess] == target)
{
return guess;
}
  
//compare three
if (arr[guess] > target)
return 3+binarySearch(arr, min, guess - 1, target);

return 3+ binarySearch(arr, guess + 1, max, target);
}
  
return 1;
}

//function to sort an array
void bubbleSort(int a[], int size)
{
//outer for loop
for(int i=0;i<size;i++)
{
//inner for loop
for (int j=0;j<size;j++)
{
if(a[i]<a[j])
{
//swap the values
int temp = a[i];
a[i]=a[j];
a[j] = temp;
}
}
}
}

int main()
{
//array declaration
int arr[1000];
  
//fill array with random number
for(int i=0; i<1000; i++)
{
//fill with random number
arr[i] = rand()%1000;
}
  
//method calling
bubbleSort(arr,1000);
  
//display the result
cout<<"The number of comparision in sequential search = "<<sequentialSearch(arr, 1000, 800);
cout<<endl<<"The number of comparision in binar search = "<<binarySearch(arr,0, 1000, 800);
  
  
return 0;
}

OUTPUT:

The number of comparison in sequential search = 1000
The number of comparison in binary search = 31