Si te exigen hacer búsqueda binaria en un arreglo desordenado no es posible... tiene que ser en un arreglo ordenado porque existen varios métodos para hacerlo como por ejemplo la búsqueda secuencial con centinela. Un sencillo ejemplo:

que dilema... si te lo dejaron de tarea pregunta a tu profesor algunos puntos criticos como los ya mensionados en este hilo.

Dulces Lunas!¡.

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.