PROWAREtech

C/C++: Binary Search Algorithm

Which is faster, iterative or recursive? They are equally blisteringly fast. Which is easier to read, iterative or recursive?

#include <iostream>
#include <ctime>
using namespace std;

#define LENGTH 200000000

// returns LENGTH when not found
unsigned long binarySearchIterative(long *arrayInts, long value)
{
	long first = 0, last = LENGTH - 1, middle;
	while (first <= last)
	{
		middle = (first + last) / 2;
		if (arrayInts[middle] == value)
			return middle;
		if (value > arrayInts[middle])
			first = middle + 1;
		else
			last = middle - 1;
	}
	return LENGTH;
}

// returns LENGTH when not found
unsigned long binarySearchRecursive(long *arrayInts, unsigned long first, unsigned long last, int value)
{
	long middle;
	if (first > last)
		return LENGTH;
	middle = first + (last - first) / 2;
	if (arrayInts[middle] == value)
		return middle;
	if (arrayInts[middle] < value)
		return binarySearchRecursive(arrayInts, middle + 1, last, value);
	else
		return binarySearchRecursive(arrayInts, first, middle - 1, value);
}

int main()
{
	long *arrayInts = new long[LENGTH];
	long start, tim, i;
	for (i = 0; i < LENGTH; arrayInts[i++] = i);

	start = clock();
	for (i = 0; i < LENGTH; i++)binarySearchIterative(arrayInts, i);
	tim = (clock() - start);
	cout << fixed << ((float)tim / 1000.0) << " seconds to binary search array (iteratively) " << LENGTH << " times" << endl << endl;

	start = clock();
	for (i = 0; i < LENGTH; i++)binarySearchRecursive(arrayInts, 0, LENGTH - 1, i);
	tim = (clock() - start);
	cout << fixed << ((float)tim / 1000.0) << " seconds to binary search array (recursively) " << LENGTH << " times" << endl << endl;

	delete[] arrayInts;
	return 0;
}

Comment