bÚsqueda binaria

5/17/2018 B SQUEDA BINARIA - slidepdf.com

http://slidepdf.com/reader/full/busqueda-binaria-55b07a94c3414 1/3

BÚSQUEDA BINARIA:

La búsqueda binaria consiste en dividir el intervalo de búsqueda en dos partes,comparando el elementos buscado con el central. En caso de no ser iguales seredefinen los extremos del intervalo (según el elemento central sea mayor o

menos que el elemento buscado) disminuyendo el espacio de búsqueda. Elproceso concluye cuando el elementos es encontrado, o bien cuando el intervalode búsqueda se anula.Este método funciona únicamente para arreglos ordenados. Con cada iteración delmétodo el espacio de búsqueda se reduce a la mitad, por lo tanto el numero decomparaciones a realizar disminuye notablemente. Esta disminución resultasignificativa cuanto mas grande sea el tamaño del arreglo. A continuación sepresenta el algoritmos de búsqueda binaria.

ALGORITMO:

Binaria (V, N, X){Este algoritmo busca al elementos X en el arreglo ordenado V de Ncomponentes}

{IZQ, CEN y DER son variables de tipo entero. BANDERA es una variable de tipobooleano}

1. Hacer IZQ1, DER N y BANDERA FALSO

2. Repetir mientras (IZQ DER) y (BANDERA = FALSO)Hacer CEN PARTE ENTERA ((IZQ + DER) /2)

2.1 Si X = V [CEN]

entonces Hacer BANDERA VERDADERA

Si no {Redefinir intervalo de búsqueda}2.1.1 Si X = V [CEN]entonces

Hacer IZQ CEN + 1Si no

Hacer DER CEN -12.1.2 {Fin del condicional del paso 2.1.1}

2.2 {Fin del condicional del paso 2.1}3. {Fin del ciclo del paso 2}

4. Si BANDERA = VERDADEROentonces

Escribir “El elemento esta en la posición CEN” Si no

Escribir “El elemento no esta en el arreglo” 5. {Fin del condicional del paso 4}



ORDENAMIENTO RÁPIDO (QUICKSORT)

El ordenamiento rápido (Quicksort en inglés) es un algoritmo basado en la técnicade divide y vencerás, que permite, en promedio, ordenar n elementos en untiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida

conocida. El algoritmo original es recursivo, pero se utilizan versiones iterativaspara mejorar su rendimiento (los algoritmos recursivos son en general más lentosque los iterativos, y consumen más recursos).El algoritmo fundamental es el siguiente:

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremospivote.

• Resituar los demás elementos de la lista a cada lado del pivote, de manera quea un lado queden todos los menores que él, y al otro los mayores. En estemomento, el pivote ocupa exactamente el lugar que le corresponderá en la

lista ordenada.• La lista queda separada en dos sublistas, una formada por los elementos a la

izquierda del pivote, y otra por los elementos a su derecha.• Repetir este proceso de forma recursiva para cada sublista mientras éstas

contengan más de un elemento. Una vez terminado este proceso todos loselementos estarán ordenados. Como se puede suponer, la eficiencia delalgoritmo depende de la posición en la que termine el pivote elegido.

• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dossublistas de igual tamaño. En este caso, el orden de complejidad delalgoritmo es O(n·log n).

• En el peor caso, el pivote termina en un extremo de la lista. El orden de

complejidad del algoritmo es entonces de 0(n²). El peor caso dependerá dela implementación del algoritmo, aunque habitualmente ocurre en listas quese encuentran ordenadas, o casi ordenadas.

• En el caso promedio, el orden es O(n·log n).No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmose centren en la elección del pivote.



Se presenta a continuación una variante del algoritmo anterior, ahora sin usar lavariable BANDERA.

Binaria (V, N, X){Este algoritmo busca al elementos X en el arreglo ordenado V de N

componentes}

{IZQ, DER y CEN son variables de tipo entero }

1. Hacer IZQ1, DER N y CEN PARTE ENTERA ((IZQ + DER) / 2)

2. Repetir mientras (IZQ DER) y (X V [CEN])Hacer CEN PARTE ENTERA ((IZQ + DER) /2)

2.1 Si X > V [CEN]entonces

Hacer IZQ CEN + 1Si no

Hacer DER CEN -12.2 {Fin del condicional del paso 2.1}

Hacer CEN PARTE ENTERA ((IZQ + DER) / 2)3. {Fin del ciclo del paso 2}4. Si IZQ > DER

entonces Escribir “El elemento no esta en el arreglo”

si noEscribir “El elemento esta en la posición CEN”

5. {Fin del condicional del paso 4}

bÚsqueda binaria

Documents