Busqueda binaria de un array desordenado

[ghastlyX]

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:

Código (cpp) [Seleccionar] Expandir

#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.

[CobraCY]

Hace algún tiempo me dejaron lo mismo como un pequeño ejercicio y esta fue la solución que propuse:

Código (cpp) [Seleccionar] Expandir


int busqueda_binaria(int *a, int inicio, int fin, int val)
{
if(inicio==fin && a[inicio] != val)
return -1;
int t= fin/2;
if(a[t] == val)
return t;
if(a[t] > val)
return busqueda_binaria(a,inicio,t-1,val);
else
return busqueda_binaria(a,t+1,fin,val);
}


Como vez esto se puede mejorar para que funcione en menos lineas, pero eso ya te lo dejo de tarea para ti .

Saludos.