Posteado por: [p3ll3] | abril 29, 2008

Busqueda binaria o búsqueda dicotómica

Busqueda binaria:

Es un algoritmo de busqueada que para realizarla, es necesario contar con un array o vector ordenado. Luego tomamos un elemento central, normalmente el elemento que se encuentra a la mitad del arreglo, y lo comparamos con el elemento buscado. Si el elemento buscado es menor, tomamos el intervalo que va desde el elemento central al principio, en caso contrario, tomamos el intervalo que va desde el elemento central hasta el final del intervalo.

Procedemos de esta manera con intervalos cada vez menores hasta que lleguemos a un intervalo indivisible, en cuyo caso el elemento no está en el vector, o el elemento central sea nuestro elemento.

De esta forma la complejidad computacional se reduce a O(ln N).

Si necesitan los Algoritmos de ordenamiento ahi se los dejo.

Yo esta busqueda la voy a hacer de manera iterativa pero se puede utilizar recursion tambien:

  public static void Buscar(int [] vect,int valor){

      int pivote = vect.length/2;       for (int i=0; i < vect.length;i++){          System.out.println(vect[i]);       }

      if (valor < pivote){

       for (int x=0;x < pivote;++x){

          if (valor == pivote){              System.out.println("Encontrado posicion "+pivote);              break;          }else if (valor == vect[x]){              System.out.println("Encontrado posicion "+x);              break;          }

       }      }else if(valor < pivote){

       for (int x=pivote;x < vect.length;++x){

          if (valor == pivote){              System.out.println("Encontrado posicion "+pivote);              break;          }else if (valor == vect[x]){              System.out.println("Encontrado posicion "+x);              break;          }

       }

      }else{          System.out.println("Elemento no encontrado >:(");      }

    }


Mas que todo les dejo el algortimo de la busqueda que es lo importante…
Espero que les sirva.

Anuncios

Responses

  1. yeah


Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Categorías

A %d blogueros les gusta esto: