Why does binary search algorithm require returning the recursive calls?-CodePudding

I was implementing recursive binary search and I ran into this problem that really confused me. Here is the code that I was initially running:

'''

int recursiveBinarySearch(int* arr, int start, int end, int key){
   int middle = (start   end) / 2;

   if (start >= end)return -1;

   if (arr[middle] == key)return middle;

   if (arr[middle] < key) {
    recursiveBinarySearch(arr, middle 1, end, key);
   }

   if (arr[middle] > key) {
    recursiveBinarySearch(arr, start, middle-1, key);
   }

}

'''

Now, as far as I understand, as soon as a base case is reached, the only thing returned should be the value that is returned from the base-case because no other call is returning anything. However, clearly I was wrong because this wasn't giving correct answers and apparently I needed a return statement infront of each of the recursive call for this algo to work, as I found out later. So my question is, why do we need to have the return statement? What exactly is the reason that my solution doesn't work?

CodePudding user response：

Let's assume, X is the function we are calling from the main function. And there is a function Y which is being called from function X. Function Y does some computation and calculates the result for X. So you should just call function Y and return it's result like below.

Y() {
 // Some computation
 return result;
}

X() {
 return Y();
}

main() {
  X();
}

Now think of it like this, each recursive call is a separate function that is doing some task. So your recursiveBinarySearch function should return the answer but it can't compute that itself, so it is calling some other functions (which in this case the same function, thus call recursion) to get the result. So it will keep calling the function and break down the problems into smaller ones until it reaches the base case where it will get the answer and finally return it.

CodePudding user response：

The reason is that C , Java and many other languages need to have a return statement (including all conditional paths the programme can follow dinamically) if the method returns something. I think that when you make the recursive call you must return the result of this call.

int recursiveBinarySearch(int* arr, int start, int end, int key){
   int middle = (start   end) / 2;

   if (start >= end)return -1;

   if (arr[middle] < key) {
    return recursiveBinarySearch(arr, middle 1, end, key);
   }

   else if (arr[middle] > key) {
    return recursiveBinarySearch(arr, start, middle-1, key);
   }

   else{
    return middle; // in that case is equal
   }

}

Answering your question the return statement is needed because of designing decisions of the language.

CodePudding user response：

There was a bug in your code where the check arr[middle]==key should be done before start>=end. Also you should return the result of recursiveBinarySearch.

This should work

int recursiveBinarySearch(int* arr, int start, int end, int key)
{
   int middle = (start   end) / 2;
   if (arr[middle] == key) return middle;
   if (start >= end) return -1;
   if (arr[middle] < key) {
      return recursiveBinarySearch(arr, middle 1, end, key);
   }
   else {
      return recursiveBinarySearch(arr, start, middle-1, key);
   }   
}

Test code: https://godbolt.org/z/8s6hWMKjj