Searching an element in a sorted array - Recursive Binary Search [O(N + log(N))].

binary_search_rec.cpp

// Problem link: https://practice.geeksforgeeks.org/problems/who-will-win/0/

#include <vector>
#include <iostream>
using namespace std;

#define ull uint64_t

bool binary_search(const vector<int> &ar, const int key, int lo, int hi) {
    // base case
    if(lo > hi) return false;
    
    int mid = lo + ((hi-lo)/2);
    
    if(ar[mid] == key)  return true;
    else if(ar[mid] > key) return binary_search(ar, key, lo, mid-1);
    else return binary_search(ar, key, mid+1, hi);
}

int main() {
	int t;  cin >> t;
	while(t--) {
	    int n, key;  cin >> n >> key;
	    vector<int> ar(n);
	    for(int i = 0; i < n; ++i)
	        cin >> ar[i];
	    
	    bool found = binary_search(ar, key, 0, ar.size()-1);
	    string ans = found == false ? "-1" : "1";
	    cout << ans << endl;
	}
	return 0;
}