Search evaluation C Look up 5000 random numbers using linea

Search evaluation - C++

Look up 5000 random numbers using linear search on the original data (original data is an array with 40,000 random numbers between 1 and 200,000), then search for 5000 numbers using the binary search, then the interpolation search.

Select your search values for each search from the list of numbers. Determine the average number of probes that each search algorithm takes.
Print out the average for the searches and their theoretical values.

Solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

int linearSearch( int* array, int size, int elem ){
   int steps = 0;
   for(; steps< size; steps++){
       if( array[steps] == elem ){ break; }}
   return steps+ 1;
}

int binarySearch( int* array, int size, int elem ){
   int low = 0;
   int high = size-1;
   int steps = 0;
   while( low <= high ){
       steps++;
       int mid = low + (high-low)/2;
       if( array[mid] == elem ){ break; }
       else if( array[mid] > elem ){ high = mid-1; }
       else{ low = mid+1; }
   }  
   return steps;
}

int interPSearch( int* array, int size, int elem ){
   int low = 0;
   int high = size-1;
   int steps = 0;
//   while( low <= high ){
    while( array[high] != array[low] && elem >= array[low] && elem <= array[high] ){

       steps++;
        int pos = low + (((double)(high -low)/(array[high]-array[low]))*(elem -array[low]));
       
        if (array[pos] == elem){break;}
        if (array[pos] < elem){ low = pos + 1; }
        else{ high = pos - 1; }
    }
    return steps;
}

int main(){

   //generate an array of 40000 random numbers
   int array[ 40000 ];
   srand( time(NULL) );
   for(int i = 0; i < 40000; i++){
       array[i] = rand()%200000 + 1;
   }
   sort( array, array + 40000 );
   //got the array
   double Lsteps = 0;
   double Bsteps = 0;
   double Isteps = 0;
   for(int i = 0; i < 5000; i++){
       int elementtoSearch = array[ rand()%40000 ];
       Lsteps += linearSearch( array, 40000, elementtoSearch );
       Bsteps += binarySearch( array, 40000, elementtoSearch );
       Isteps += interPSearch( array, 40000, elementtoSearch );
   }

   Lsteps = Lsteps/5000;
   Bsteps = Bsteps/5000;
   Isteps = Isteps/5000;

   cout << \"Average number of probes Theoritical Values \"<< endl;
   cout << \"For Linear Search: \" << endl;
   cout << \"Average number of probes: \" << Lsteps << endl;
   cout << \"Theoritical value: \" << 20000 << endl << endl;

   cout << \"For Binary Search: \" << endl;
   cout << \"Average number of probes: \" << Bsteps << endl;
   cout << \"Theoritical value: \" << 15.287 << endl << endl; //log2(40000)

   cout << \"For Interpolation Search: \" << endl;
   cout << \"Average number of probes: \" << Isteps << endl;
   cout << \"Theoritical value: \" << 3.934 << endl; //log2(log2(40000))

   return 0;
}