# PROWAREtech

articles » current » c-plus-plus » algorithms » binary-search

## C/C++: Binary Search Algorithm

A very fast search algorithm if working with arrays.

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

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;
}

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;
}
``````