Implement a binary search function in three substantially different programming languages. In each program (identical, except for the programming language), carry out the same 10,000,000 unsuccessful searches for eight different-sized arrays, namely arrays of sizes 128, 512, 2048, 8192, 32768, 131072, 524288, and 2,097,152. Measure in each of the three programs the time it takes to do the 10,000,000 searches for each of the eight arrays. Compare these timings to the theoretical timings the algorithm binary search provides. Are there differences between the three programs? Explain your timings and observations!!

The code to this question can be defined as follows:

Explanation:

C language code:

#include <stdio.h>//defining header file

int binarySearch(int x[], int l, int y, int z)//defining method binarySearch that accepts four integer parameter

{

if (y >= l)//defining if block that check r value is greater the l  

{

int m= l + (y - l)/2; //defining if block that holds mid value of array  

if (x[m] == z)//use if block  that check value in array

return m;// return array value

if (x[m] > z) //defining if block that check array value greater then x value

return binarySearch(x, l, m-1, z);//use return keyword to call method

return binarySearch(x, m+1, y, z);// in else it use return keyword to call method

}

return -1;//return value -1

}

int main()//defining main method

{

int x[] = {2, 3, 4, 10, 40};//defining array that hold integer values  

int n = sizeof(x)/ sizeof(x[0]);//use n variable to hold its size value

int z = 10;//defining x varaiable that hold integer value

int r= binarySearch(x, 0, n-1, z);//use r varaiable to hold method return value

if(r== -1) //defining if block that check its value equal to -1  

printf("Number is not foud in array ");//print message

else

printf("Number is present at %d position", r);//print value

return 0;

}

C++ language code:

#include <iostream>// header file

using namespace std;

int binarySearch(int x[], int l, int y, int z)//defining method binarySearch that accepts four integer parameter

{

if (y >= l)//defining if block that check r value is greater the l

{

int m= l + (y - l)/2; //defining if block that holds mid value of array

if (x[m] == z)//use if block  that check value in array

return m;// return array value

if (x[m] > z) //defining if block that check array value greater then x value

return binarySearch(x, l, m-1, z);//use return keyword to call method

return binarySearch(x, m+1, y, z);// in else it use return keyword to call method

}

return -1;//return value -1

}

int main()//defining main method

{

int x[] = {2, 3, 4, 10, 40};//defining array that hold integer values

int n = sizeof(x)/ sizeof(x[0]);//use n variable to hold its size value

int z = 10;//defining x varaiable that hold integer value

int r= binarySearch(x, 0, n-1, z);//use r varaiable to hold method return value

if(r== -1) //defining if block that check its value equal to -1

cout<<"Number is not foud in array ";//print message

else

cout<<"Number is present at position "<< r;//print value

return 0;

}

Python language code:

def binarySearch (a, x, r, y):#defining a method binarySearch

   if r >= x:#defining if block that checks r is greater than equal to x

       m = x + (r - x)//2#defining m variable that hold mid value

       if a[m] == y:#use if that check its input value equal y

           return m#return m value

       elif a[m] > y:#use array that check its value greaterthan y  

           return binarySearch(a,x, m-1, y) #use return keyword to call method

       else:#defining else block

           return binarySearch(a, m+1, r, y)#use return keyword to call method

   else:  #defining else block  

       return -1#return value -1

a = [ 2, 3, 4, 10, 40 ]#defining list a that holds value

y = 10#defining integer variable

r = binarySearch(a, 0, len(a)-1, y)#defining r variable that holds method value

if r != -1:#use if that check r is not equal to -1

   print ("Number is available at ", r," position")#print value

else:#else block

   print ("Number is not available in array")#print message