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.

2 Use any sorting algorithm to sort list.

Answer 1

Time complexity: sequential search = O(n), Binary Search = O(logn)

code:  

#include <iostream>
#include <ctime>
#include <unistd.h>
using namespace std;

static int comparison = 0;

int binarySearch(int arr[], int num, int lo, int hi)
{
    if(lo <= hi)
    {
        int mid = lo + (hi - lo)/2;
        comparison = comparison + 1;
        if(num == arr[mid])
        {

            return mid;
        }

        if(num < arr[mid])
        {
            return binarySearch(arr,num,lo,mid-1);
        }
        if(num > arr[mid])
        {
            return binarySearch(arr,num,mid+1,hi);
        }
    }
    return -1;
}

int main()
{
    int arr[1000];
    srand(time(0));
    for(int i = 0; i < 1000; i++)
    {
        arr[i] = int(rand()/10);
    }
    //cout << arr[100]; 
    int temp;

    int num;
    int found;
    //int comparison;
    cout << "Enter the number to search: " <<endl;
    cin >> num;
    cout << "Performing sequential search..." <<endl;
    bool fo = false;
    int i = 0;
    for(i = 0; i < 1000 && !fo; i++)
    {
        if(num == arr[i])
        {
            fo = true;
        }
    }
    if(i == 1000)
    {
        cout << " Your number " << num << "not present!" <<endl;
    }else
    {
        cout << " Your number " << num << " found at index: " << i-1 << " using sequential search by comparing " << i << " elements" << endl;
    }

    for(int i1 = 0; i1 < 1000; i1++) // sorting the array to apply binary search, using bubble sort
    {
        for(int j1 = 1; j1 < 1000; j1++)
        {
            if(arr[j1-1] > arr[j1])
            {
                temp = arr[j1-1];
                arr[j1-1] = arr[j1];
                arr[j1] = temp;
            }
        }
    }
    cout << "\n \n Performing binary search..." << endl;
    sleep(1);
    found = binarySearch(arr, num, 0 , 999);

    if(found == -1)
    {
        cout << "Your number not present!";
    }else
    {
        cout << "your number " <<num <<  " found after comparing  " << comparison << " numbers using binary search.";
    }

    return 0;
}