Busqueda Binaria 09/07

[GitMory]

`#include < iostream>

include < vector>

include < algorithm>

include < cstdlib>

include < ctime>

using namespace std;

vector generarLista(int tamano, int min, int max) { vector lista(tamano); srand(time(0)); for (int i = 0; i < tamano; ++i) { lista[i] = min + rand() % (max - min + 1); } return lista; }

vector busquedaBinaria(const vector& lista, int numero) { vector posiciones; int izquierda = 0; int derecha = lista.size() - 1;

while (izquierda <= derecha) {
    int medio = izquierda + (derecha - izquierda) / 2;

    if (lista[medio] == numero) {
        posiciones.push_back(medio);

        int i = medio - 1;
        while (i >= 0 && lista[i] == numero) {
            posiciones.insert(posiciones.begin(), i);
            --i;
        }

        int j = medio + 1;
        while (j < lista.size() && lista[j] == numero) {
            posiciones.push_back(j);
            ++j;
        }
        break;
    }
    if (lista[medio] < numero) {
        izquierda = medio + 1;
    } else {
        derecha = medio - 1;
    }
}

return posiciones;

}

int main() { vector lista = generarLista(200, 1, 1000); sort(lista.begin(), lista.end()); cout << "Lista generada: "; for (int numero : lista) { cout << numero << " "; } cout << endl;

int numero;
cout << "Ingrese el numero a buscar: ";
cin >> numero;

vector<int> posiciones = busquedaBinaria(lista, numero);

if (posiciones.empty()) {
    cout << "El numero " << numero << " no se encuentra en la lista" << endl;
} else {
    cout << "El numero " << numero << " aparece " << posiciones.size() << " veces en las posiciones: ";
    for (int pos : posiciones) {
        cout << pos << " ";
    }
    cout << endl;
}

return 0;

} `