More efficient way to do binary search in c++?

Question

I am doing a question on Binary Search using C++, but I was wondering if there is a more efficient way to implement it.

My code is as follows:

int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
 
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] > x) {
            return binarySearch(arr, l, mid - 1, x);
        } else {
            return binarySearch(arr, mid + 1, r, x);
        }
    } else {
        return -1;
    }
}

Answer 1

I am a proponent of binary search without comparison for equality, so that every reduction step takes a single comparison (you perform a single comparison for equality in the end, when the interval has shrunk).

The idea of comparison for equality is that you can terminate the search earlier when the key is found. If the key is found at depth d, this takes 2d comparisons. The average number of comparisons is twice the average depth of the tree, and is 2 Log2(N) - 1 for a perfect tree (early termination only spares one comparison).

This is to be compared to Log2(N) without equality test. Not counting that when the key is not found, the full depth of the tree is always traversed ! Testing for equality seems a false good idea.