Program to demonstrate time and space complexity in binary and linear searching

   

#include < iostrea m>
#include < iomanip >
 
using namespace std;
int linearcount=0;
int binarycount=0;
int linearsearch(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++){
        if (arr[i] == x)
            return i;
    linearcount++;
}
    return -1;
}

int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 

binarycount++;
    } 
 
    return -1; 
} 


int main()
{
  

    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]); 
 



 
cout<< "Binary Search"<< endl;
   int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 


 

cout<< endl<<"Time :" << binarycount<< endl;


cout<< endl<< endl;

cout<< "Linear Search"<< endl;
   result = linearsearch(arr, n, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;

    cout<< endl<< "Time :" << linearcount<< endl;
 cout<< endl;

return 0;
}