How would I Re-write the following binary search function so that it uses recursion

[shanno8]

int binary_search(int arr[], int find, int low, int high)
{
int middle;

while(low <= high) {
middle = (low + high) / 2;
if (arr[middle] < find) low = middle;
else if (arr[middle] > find) high = middle;
else return middle;
}

return -1;
}

[Repeater]

The key is to realise that the purpose of the recursive function is now to either return the location of the item being searched for, or to call itself again.

Then, we can write the cases simply. It will be something like this:

int binary_search(int arr[], int find, int low, int high)
{
  int middle = low + (high-low)/2;

  //  if low == high and we haven't found what we want, return -1
  
  // if middle is the right answer, return it

  // if middle is too high, call function again, with same low but high=middle

  // if middle is too low, call function again, with same high but low=middle
}

[lastchance]

@shanno8,

Irrespective of recursion, your algorithm will fail sometimes.

Try arr[] = { 1, 2, 3 } and search for value 3. It will actually cycle indefinitely or, in the case of recursion, blow the stack.

[dhayden]

Building on lastchance's observation, I suggest that you make the invariant:
array[low] <= find < array[high]
In other words, the index, if it exists is greater than or equal to low, but less than high. Then the loop becomes
while (low < high) ... and it always converges.

[lastchance]

I was thinking more along the lines of updates
low=middle+1
and
high=middle-1

Otherwise, integer division for the example I gave would leave you stuck indefinitely on
low=1, high=2,
with middle continually being evaluated as 1.

[lastchance]

#include <iostream>

int binsearch( int A[], int value, int low, int high )
{
   if ( low > high ) return -1;

   int mid = ( low + high ) / 2;
   if      ( A[mid] == value ) return mid;
   else if ( A[mid]  < value ) return binsearch( A, value, mid + 1, high    );
   else                        return binsearch( A, value, low    , mid - 1 );
}

int main()
{
   int A[] = { 1, 2, 3, 5, 8, 11 };
   int N = sizeof A / sizeof A[0];
   int value = 12;
   std::cout << binsearch( A, value, 0, N - 1 );
}