Question

Search Benchmarks

No Pointers or Vectors can be used for this program. Do not use exit, break, swap, or sort functions from C++.

Write a program to generate an array of 100 random three-digit integers (100 – 999). The program should display the array values (formatted as columns, ten items per line).

Once the numbers are generated, the user should be prompted for the search item. The program should use a linear search to find the item. The program should keep track of the number of comparisons made and whether or not the item was found.

The program should then sort the array (using the sort algorithm of your choice), display the sorted array, and then repeat the search using a binary search. Again, the program should report the number of comparisons made (not the spot it is found).

This program will make use of at least five functions:

void displayArray(int [], int) passing the array and the size of the array

void randomizeArray(int [], int) passing the array and the size of the array

void sortArray(int [], int) passing the array and the size of the array

void sequentialSearch(int [], int, int) passing the array, the size of the array, and the search item

void binarySearch(int [], int, int) passing the array, the size of the array, and the search item

The two search functions have return type void, as they must provide two different pieces of information (the number of comparisons made, and whether or not the item was found). Therefore these functions will use cout statements to provide this information.

Must use functions, no C-string function, no <bits/stdc++.h> . Only 1 return per function or main program.

Answer 1

#include <iostream>

using namespace std;

void displayArray(int arr[] , int len) {
 for(int i=0;i<100;i++){
    if(i%10==0)
      cout<<endl;
    cout<<arr[i]<<" ";
  }
}

void randomizeArray(int arr[], int len){
   int num;
  for(int i=0;i<100;i++){
     num = (rand() % (100 - 999 + 1)) + 100;
    arr[i] = num;
  }
}

//sorting using insertion sort
void sortArray(int arr[], int n){ 
    int i, key, j;  
    for (i = 1; i < n; i++) 
    {  
        key = arr[i];  
        j = i - 1;  
        while (j >= 0 && arr[j] > key) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
}  


void sequentialSearch(int arr[], int size, int num){
  int num_comp = 0;
  for(int i=0;i<size;i++){
    num_comp++;
    if(arr[i]==num){
      cout<<"Element FOUND!!!. Number of comparisons = "<<num_comp<<endl;
      return;
    }
  }
  cout<<"Element NOT FOUND!!! Number of comparisons = "<<size<<endl;
}
int BS_comp_count = 0;
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
      BS_comp_count++;
        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; 
} 
void binarySearch(int arr[],int size, int num){
  int index = binarySearch(arr, 0, 99, num);
  if(index!=-1){
    cout<<"Element FOUND!!!. Number of comparisons = "<<BS_comp_count<<endl;
  }
  else
   cout<<"Element NOT FOUND!!! Number of comparisons = "<<BS_comp_count<<endl;
}
int main() {
  int arr[100];
  cout<<"generating random array...";
  randomizeArray(arr,100);
  cout<<"\nRandomly generated array is:\n";
  displayArray(arr,100);
  cout<<"\nEnter number to search: ";
  int num;
  cin>>num;
  cout<<"\n---Search using Sequential search---"<<endl;
  sequentialSearch(arr, 100, num);
  cout<<"Sorted array is:\n";
  sortArray(arr, 100);
  displayArray(arr, 100);
  cout<<"\n---Search using Binary search---"<<endl;
  binarySearch(arr, 100, num);
}

Sample output for the above code is as following:

Sample Output 1:

Sample Output 2:

Note - any doubt/query do ask in comment section and please LIKE the solution