Question

C++Design and implement a program (name it LinearBinarySearch) to implement and test the linear and binary search algorithm discussed in the lecture slides. Define method LinearSearch() to implement linear search of an array of integers. Modify the algorithm implementation to count number of comparisons it takes to find a target value (if exist) in the array. Define method BinarySearch() to implement binary search of an array of integers. Modify the algorithm implementation to count number of comparisons it takes to find a target value (if exist) in the array. Now, develop a test method to read integer values from the user in to an array and then call methods LinearSearch() and BinarySearch() and printout the number of comparison took to find the target values using each search method. Document your code and organized your outputs as follows: Arrays Values: Target value: Linear Search Comparisons: Binary Search Comparisons:

Answer 1

#include <iostream>

using namespace std;
#define SIZE 20
// performs linear search on the array and returns number of comparisons
   // required
   int linearSearch(int aA[], int aEle) {
       for (int i = 0; i < SIZE; i++) {
           if (aA[i] == aEle)
               return i + 1;
       }
       return -1;
   }
void bubbleSort(int array[],int n) {

       int i, j, temp;
       for (i = 0; i < n - 1; ++i) {

           for (j = 0; j < n - 1 - i; ++j) {

               if (array[j] > array[j + 1]) {

                   temp = array[j + 1];

                   array[j + 1] = array[j];

                   array[j] = temp;
               }

           }

       }
   }

   // performs binary search on the array and returns the number of
   // comparisions
   int binarySearch(int arr[], int l, int r, int x, int comp) {

       if (r >= l) {
           comp++;
           int mid = l + (r - l) / 2;
           if (arr[mid] == x) {
               return comp;
           }
           if (arr[mid] < x)
               return binarySearch(arr, mid+ 1, r, x, comp);

           return binarySearch(arr, l, mid - 1, x, comp);
       }
       return comp;
   }

   int main() {
       int *a= new int[SIZE];
       int *b = new int[SIZE];
       for (int i = 0; i < SIZE; ++i) {
           a[i] = rand()%1000;
           // copying values into array
           b[i] = a[i];
       }
       bubbleSort(a,SIZE);
       // printing array
       for (int i = 0; i < SIZE; ++i) {
           cout<<b[i] << " ";
       }
       // reading element to search in the array
       cout<<"\nEnter element to search: ";
       int ele;
       cin>>ele;
       // calling binary and linear search
       cout<<binarySearch(a, 0, SIZE, ele, 0) << " comparisions required to find " << ele
               << " using binary search\n";
       cout<<linearSearch(b, ele) << " comparisions required to find " << ele << " using linear search\n";

   }

Note : Please comment below if you have concerns. I am here to help you

If you like my answer please rate and help me it is very Imp for me