Foro de elhacker.net

Necesito hacer un código que haga la busqueda binaria de un array no ordenado. Entiendo el código usual pero a la hora de discriminar entre los dos sub-arrays no se muy bien que hacer.

La búsqueda binaria la puedes aplicar cuando tienes una función de entrada (en tu caso un array) que es monótona. Si el array no está ordenado, una búsqueda binaria no es correcta por motivos evidentes si entiendes como funciona con un array ordenado. Si quieres buscar un elemento en concreto necesitarás hacer una búsqueda lineal.

El algoritmo lo que hacer es dividir recursivamente el array en dos partes iguales, hasta llegar al caso base que es que el array tenga un elemento

Hola

Pero si el array no está ordenado qué criterio utilizas para dividirlo??

Saludos

Siempre en dos mitades iguales. Ejemplo:
[5,7,8,3,4,9,1,3] se divide [5,7,8,3] y [4,9,1,3]. A su vez [5,7,8,3] se divide en [5,7] y [8,3]. [5,7] se divide en [5] y [7], con arrays de un elemento que es el caso base.

El problema es como implementar todo ese algoritmo en C.

Como bien dijo ghastlyX hay que tener un array ordenado, el procedimiento el cual me enseñaron es hacer una ordenacion tipo Bubble, i cuando terminas puedes hacer la busqueda binaria, en otro caso la unica solucion es una busqueda lineal.

Divides el array en 2 i compruebas si el elemento que busquas es > o < que el elemento que has utilizado para dividir el array EJ.

Suponemos un array ordenado:

2245566789 i buscamos el 8 entonces primero

2245 /5/ 66789 el elemento top(numero de elementos/2) (el segundo 5)
es el elemento que buscas?? => NO
es menor o mayor? = menor entonces tiene que estar en el array de la derecha

66789 => 66 /7/ 89

es el elemento que buscas?? => NO
es menor o mayor? = menor entonces tiene que estar mas a la derecha

|8| / 9
es el elemnto que buscas?? => SI

Puedes hacer busqueda binaria en un arreglo desordenado!

Solo necesita crear un arreglo de índices y ordenalo usando el arreglo de valores.

Bueno, voy avanzando, ya tengo el código:

int buscaElemento(int n, const Vector v, int inf, int sup){
   double res1;
   double res2;
   double res = -1.0;

   if(sup-inf == 0){
      if(v[inf] == n){
         res = inf;
      }
   } else {
        res1 = buscaElemento(n, v, inf, sup-inf/2);
        res2 = buscaElemento(n, v, (sup-inf/2)+1, sup);
   }

   if(res1 != -1.0){
      res = res1;
   } else if(res2 != -1.0){
      res = res2;
   }

   return res;
}

El problema ahora es que no funciona, se pilla el programa, supongo que será por las conversiones entre int y double no?

Como ya dije antes, si el array está desordenado, NO se puede hacer una búsqueda binaria, puesto que sería incorrecta. Si tienes que hacer una binaria por algún motivo, lo tendrás que ordenar antes.

Así que por mucho que lo intentes, el código es imposible que funcione sobre un vector desordenado.

Realizar una búsqueda binaria en un array desordenado es totalmente absurdo.

Ya expliqué como es el algoritmo. Se qué es absurdo, pero es lo que me han pedido en la facultad xD

David_RM, tienes que hacer lo seguiente:

Solo necesita crear un arreglo de índices y ordenalo usando el arreglo de valores.

int arreglo[] = { 9 5 2 1};
int idxs[] = { 3 2 1 0 }

Hablé esto, pero tu no había visto.

Es como dice LearningSpanishProgrammer para implementar búsqueda binaria tienes que tener el arreglo en orden de alguna u otra manera. Con indices estaría bien.

Pues yo creo que quisieron que usaras tu materia GRIS...

Primero ordena el array... despues aplicas el proceso de ordenacion binaria!¡.

Dulces Lunas!¡.

No se puede ordenar. De todas formas, gracias a todos

InsertSort?

Dulces Lunas!¡.

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:

Igual no es busquedad binaria, el algoritmo ya lo explique anteriormente

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

Dulces Lunas!¡.

Os dejo el enunciado, el algoritmo ya lo explique antes:

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.

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

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.