Pero eso no es búsqueda binaria, puesto que necesariamente tendrás que explorar en caso peor las dos mitades y tendrá complejidad lineal.

Una posible implementación de lo que te piden de forma algo cutre sería la siguiente:

#include <iostream>
#include <vector>
using namespace std;
 
int busca(int x, vector<int>& v, int a, int b) {
    if (a == b) return (v[a] == x) ? a : -1;
    return max(busca(x, v, a, (a + b)/2), busca(x, v, (a + b)/2 + 1, b));
}
 
int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    int x;
    while (cin >> x) cout << busca(x, v, 0, n - 1) << endl;
}

Y son dos líneas de código la función. Sin embargo, se podría optimizar la función, para que por ejemplo si la primera llamada recursiva encuentra el elemento, no haga la segunda llamada.