Question

Write a program in C++ to find the number of comparisons using binarySearch and the sequential search algorithm as follows:

Suppose list is an array of 1000 elements.

a. Use a random number generator to fill list.

b. Use any sorting algorithm to sort list.

c. Search list for some items as follows:

i. Use the binary search algorithm to search the list. (You may need to modify the algorithm given in this chapter to count the number of comparisons.)

ii. Use the binary search algorithm to search the list, switching to a sequential search when the size of the search list reduces to less than 15. (Use the sequential search algorithm for a sorted list.)

Comments would be appreciated! Am a relatively new coder. Thank you.

Answer 1

The Code below will help you generate the required output.

main.cpp

#include <iostream>

using namespace std;

// static function to count number of comparisons
static int count = 0;
//function for linear search or sequential search

int search(int arr[], int n, int x)
{
count++;
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
  

// utility function to swap two numbers
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
  
// Bubble sort : sorting array
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
  
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}

// Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

int binarySearch(int arr[], int l, int r, int x)
{
count++;
if (r >= 15) {
int mid = l + (r - l) / 2;
  
// If the element is present at the middle
if (arr[mid] == x)
return mid;
  
// If element is smaller than mid, then search lst sub array
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
  
// Else the element can only be present in right sub array
return binarySearch(arr, mid + 1, r, x);
}
else // switch to sequential search
{
return search(arr,(r-l),x);
}

// Not in array of numbers
return -1;
}

int main()
{
//variables
int numberOfElements = 1000;
int *numbers = new int[numberOfElements];
int x;
// Use current time as seed for random generator
srand(time(0));
  
// generating numbers between 1 and 10000
for(int i = 0; i<numberOfElements; i++)
numbers[i] = rand() % 10000 + 1;

bubbleSort(numbers,numberOfElements);   
//displaying array
printArray(numbers,numberOfElements) ;
  
// user input to search element
cout<<"element to Search : " ;
cin>> x;
  
// calling function to search x
int result = binarySearch(numbers, 0, numberOfElements-1, x);
  
cout<<"Number of Comparisons : "<<count<<endl;
cout<<"Position of element in array is : "<<result<<endl;
}

OUTPUT