Question

In C++:

In this lab we will creating twos arrays of Generic objects, searching through those arrays using BINARY and SEQUENTIAL sorts, calculate the run-time of each method, and determine the BIG O, OMEGA and THETA notation.

In our object we should have some way to compare elements to determine if one element is LESS THAN, GREATER THAN, and EQUAL TO. After this Generic Class is defined with a method that allows for comparison is completed, then you will create 2 arrays, one which is unsorted, the other which is sorted from the smallest to the largest element.

You will write one method that performs the SEQUENTIAL SEARCH for an individual element on an array. This method should be named SequentialSearch, and should take in the parameters of an Generic array and a Generic Element to be searched for. If the element exist in the array return its index, if the element doesn't exist return -1.

You will write one method that performs the BINARY SEARCH for an individual element on an array. This method should be named BinarySearch, and should take in the parameters of an Generic array and a Generic Element to be searched for. If the element exist in the array return its index, if the element doesn't exist return -1.

You will also count the number of operations that is performed in each method and will calculate the RUN-TIME of each method, as well as calculating the BIG O, OMEGA and THETA notation of each method. This information should be written in a comment block before each method ( you may count the number of operations on each line if you want ).

You are required to write self commenting code for this Lab, refer to the Google Style Sheet if you haven't become familiar with it.

Answer 1

#include <bits/stdc++.h>
using namespace std;

// The time complexity of Sequential Search is O(n), Theta(n), Omega(1).
// Best case when srch is present at the beginning
int SequentialSearch(int arr[], int n, int srch)
{ 
    int i, count=0; 
    for (i = 0; i < n; i++)
        {
                count++;
                // Check if srch is present at ith place
        if (arr[i] == srch) 
        {
                cout<<"Total operations used using Sequential search: "<<count<<endl;
            return i; 
                }
        }        
    // if we reach here, then element was not present
        cout<<"Total operations used using Sequential search: "<<count<<endl; 
    return -1; 
} 

// The time complexity of Binary Search is O(log n), Theta(log n), Omega(1).
// Best case when srch is present at middle
int BinarySearch(int arr[], int l, int r, int srch) 
{ 
        int count=0;
    while (l <= r) 
        { 
                count++;
        int m = l + (r - l) / 2; 
  
        // Check if srch is present at mid 
        if (arr[m] == srch)
                {
                        cout<<"Total operations used using Binary search: "<<count<<endl;
                        return m;
                } 
  
        // If srch greater, ignore left half 
        if (arr[m] < srch) 
            l = m + 1; 
  
        // If srch is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was not present
        cout<<"Total operations used using Binary search: "<<count<<endl; 
    return -1; 
}

void printArray(int array[], int n)
{
        for(int i=0; i<n; i++)
        {
                cout<<array[i]<<" ";
        }
        cout<<endl;
}

int main()
{
        int n=10, res1, res2, val1, val2;
        cout<<"Sequential Search...\n";
        int arr[]={9, 39, 20, 11, 32, 45, 67, 82, 1, 96};
        sort(arr, arr+n);
        printArray(arr, n);
        res1 = SequentialSearch(arr, n, 82);
        if(res1==-1)
                cout<<82<<" is not present!";
        else
                cout<<82<<" found at index: "<<res1<<endl;
                
        cout<<"Binary Search...\n";
        int brr[]={46, 63, 77, 91, 51, 30, 12, 8, 99, 75};
        sort(brr, brr+n);
        printArray(brr, n);
        res2 = BinarySearch(brr, 0, n, 77);
        if(res2==-1)
                cout<<77<<" is not present!";
        else
                cout<<77<<" found at index: "<<res2<<endl;
        
        return 0;
}

I have typed everything in the code itself. Hope it will help.

If you require anything else post it in the comment section please.

Good Luck :)