Hello,
I have a problem for my Data Structures and Algorithms class
that involves running a binary search in three different programming
languages, C++, C, and Java.
I am supposed to carry out 1,000,000 unsuccessful searches on arrays of
sizes: 128; 512; 2,048; 8,192; 32,768; 131,072; 524,288; 2,097,152.
Then I am supposed to measure the timings for each of these algorithms
in wall clock time. I chose to measure only the time required for the
1,000,000 unsuccessful searches, and not the entire program.
However, after running both my Java and C++ programs, I noticed that my
C++ timings were 10 times the size of my Java timings. Which seemed odd
to me, I thought I remembered being taught that C++ is the leaner of the
two languages.
Does anyone have any insight into this?
If it helps, here is my code in C++ and Java, both timings are measured
in milliseconds.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <Windows.h>
#include <iostream>
int binarySearch(int [], int, int, int);
int main()
{
const int NUMBER_OF_ELEMENTS = (2097152);
int a[NUMBER_OF_ELEMENTS];
for(int i = 0; i < NUMBER_OF_ELEMENTS; i++)
{
a[i] = i;
}
DWORD start, end;
start = GetTickCount();
for(int i = 0; i < 1000000; i++)
binarySearch(a, 50, 0, (NUMBER_OF_ELEMENTS  1));
end = GetTickCount();
std::cout << "Elapsed time: " << (double)(end  start);
std::cin.get();
}
int binarySearch(int arrayToBeSearched[], int value, int min, int max)
{
if(max < min)
return 1;
else
{
int mid = (int)((min + max) /2 );
if (arrayToBeSearched[mid] > value)
return binarySearch(arrayToBeSearched, value, min, (mid  1));
else if(arrayToBeSearched[mid] < value)
return binarySearch(arrayToBeSearched, value, (mid + 1), max);
else
return mid;
}
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public class Main
{
public static void main(String[] args)
{
final int ARRAY_SIZE = (2097152);
int[] testArray = new int[ARRAY_SIZE];
for(int i = 0; i < ARRAY_SIZE; i++)
{
testArray[i] = i;
}
long start = System.currentTimeMillis();
for(int i = 0; i < 1000000; i++)
{
binarySearch(testArray, 10, 0, ARRAY_SIZE  1);
}
long end = System.currentTimeMillis();
System.out.println("Execution time: " + (end  start));
}
public static int binarySearch(int[] A, int key, int min, int max)
{
if(max < min)
return 1;
else
{
int mid = (int)((max + min) / 2);
if(A[mid] > key)
return binarySearch(A, key, min, mid  1);
else if (A[mid] < key)
return binarySearch(A, key, mid + 1, max);
else return mid;
}
}
}
