Question

implement a binary search function in 3 programming languages. In each program (identical, except for the programming language), carry out the same 20,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 20,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!!

Answer 1

C
--

#include <stdio.h>

// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;

// If the element is present at the middle itself
if (arr[mid] == x) return mid;

// If element is smaller than mid, then it can only be present
// in left subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

// Else the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
}

// We reach here when element is not present in array
return -1;
}

int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}

java
-----
class BinarySearch
{
// Returns index of x if it is present in arr[l..r], else
// return -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid = l + (r - l)/2;

// If the element is present at the middle itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then it can only
// be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);

// Else the element can only be present in right
// subarray
return binarySearch(arr, mid+1, r, x);
}

// We reach here when element is not present in array
return -1;
}

// Driver method to test above
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = {2,3,4,10,40};
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr,0,n-1,x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index "+result);
}
}

python
------
def binarySearch (arr, l, r, x):

# Check base case
if r >= l:

mid = l + (r - l)/2

# If element is present at the middle itself
if arr[mid] == x:
return mid

# If element is smaller than mid, then it can only
# be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)

# Else the element can only be present in right subarray
else:
return binarySearch(arr, mid+1, r, x)

else:
# Element is not present in the array
return -1

# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binarySearch(arr, 0, len(arr)-1, x)

if result != -1:
print "Element is present at index %d" % result
else:
print "Element is not present in array"

What do you t