Ordered Binary Search w/ Assembly | Recursive vs. Iterative vs. Library
<p>Which is better?</p>

<p>According to Savitch, each recurse is saved on the stack in the form of an activation frame.  This has overhead.  However it takes a few less lines of code to write a recursive version.  For an interview which one is better to turn in.  The code for both is below.</p>

<pre><code>#include &lt;iostream&gt;

using namespace std;
const int SIZE = 10;
int array[ SIZE ] = { 0,1,2,3,4,5,6,7,8,9 };
int answer = NULL;

void binary_search_recursive( int array[], int start, int end, int value, int&amp; answer )
{
    int mid = (start + end ) / 2;

    if ( array[ mid ] == value )
    {
        answer = mid;
    }
    else if ( array[ mid ] &lt; value )
    {
        binary_search_recursive( array, mid + 1, end, value, answer );
    }
    else
    {
        binary_search_recursive( array, start, mid - 1, value, answer );
    }
}

void binary_search_iterative( int array[], int start, int end, int value, int&amp; answer )
{
    int mid = ( (start + end ) / 2 );

    while( array[ mid ] != value  )
    {
        if ( array[ mid ] &lt; value )
        {
            start = mid; 
            mid = ( ( ( mid + 1 ) + end ) / 2 );
        }
        else
        {
            end = mid;
            mid = ( ( start + ( mid - 1 ) ) / 2 );
        } 
    }
    answer = mid;
}

int main()
{
    binary_search_iterative( array, 0, SIZE - 1, 4, answer);
    cout &lt;&lt; answer;
    return 0;
}
</code></pre>
