Question

How to implement recursive binary search in C++

Answer 1

#include <iostream>
 
using namespace std;
 
int recursive_binary_search(int arr[], int left, int right, int to_find) { 
    if (right >= left) { 
        int mid = left + (right - left) / 2; 
  
        if (arr[mid] == to_find) 
            return mid; 
    
        if (arr[mid] > to_find) 
            return recursive_binary_search(arr, left, mid - 1, to_find); 
    
        return recursive_binary_search(arr, mid + 1, right, to_find); 
    } 
  
    return -1; 
} 
 
int main() {
    int arr[] = { 2, 3, 6, 7, 12, 15, 17, 19 }; 
    int to_find = 7; 
      
    int i = recursive_binary_search(arr, 0, sizeof(arr)/sizeof(arr[0]) - 1, to_find); 
      
    (i == -1) ? cout << "not found" : cout << "Found at index: " << i; 
}
 
 
 
/*
run:
 
Found at index: 3
 
*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
 
using namespace std;
 
int recursive_binary_search(int arr[], int left, int right, int to_find) {
   int mid = (left + right) / 2;
   if (left > right) return -1;
   if (arr[mid] == to_find) return mid;
     
   if (arr[mid] < to_find) 
        return recursive_binary_search(arr, mid + 1, right, to_find);
   else
        return recursive_binary_search(arr, left, mid-1, to_find);
} 
 
int main() {
    int arr[] = { 2, 3, 6, 7, 12, 15, 17, 19 }; 
    int to_find = 7; 
      
    int i = recursive_binary_search(arr, 0, sizeof(arr)/sizeof(arr[0]) - 1, to_find); 
      
    (i == -1) ? cout << "not found" : cout << "Found at index: " << i; 
}
 
 
 
/*
run:
 
Found at index: 3
 
*/

 

70+ SQL courses for beginners and professionals