168 Shares 8612 views

La búsqueda binaria – una de las maneras más fáciles de encontrar un elemento en una matriz

Muy a menudo, los programadores, incluso los principiantes, se enfrentan con el hecho de que hay un conjunto de números, que debe encontrar un número específico. Es esta colección se llama una matriz. Y para encontrar elementos en ella, hay una miríada de formas. Pero el más simple de ellos puede considerarse una búsqueda binaria a la derecha. ¿Qué es este método es? Y cómo implementar la búsqueda binaria? Pascal es el entorno más fácil para la organización de un programa de este tipo, por lo que vamos a utilizar para estudiar.

En primer lugar, analizar, ¿cuáles son las ventajas de este método, es por lo que podemos entender, ¿cuál es el punto en el estudio del tema. Por lo tanto, vamos a tener una matriz con una dimensión de al menos 100000000 elementos, que deben encontrar alguna. Por supuesto, este problema puede resolverse fácilmente mediante una simple búsqueda lineal, en el que estamos usando el ciclo comparará el elemento requerido con todos aquellos que están en la matriz. El problema es que la aplicación de esta idea va a tomar mucho tiempo. En un sencillo programa de Pascal en varios tratamientos, y tres líneas del texto principal, no se dará cuenta de ello, pero cuando llegamos a unos proyectos más o menos grande, con un gran número de ramas y una buena funcionalidad, el programa estará listo para ser cargado durante demasiado tiempo. Sobre todo si el equipo es un débil desempeño. Por lo tanto, hay una búsqueda binaria, lo que reduce el tiempo de buscar por lo menos dos veces.

Así que, ¿cuál es el principio de funcionamiento de este método? Inmediatamente se debe decir que la búsqueda binaria trabaja no está en cualquier matriz, pero sólo en un conjunto ordenado de números. En cada elemento medio paso dado de la matriz (es decir, el número del elemento). Si el requerido número es mayor que el promedio, entonces todo lo que queda, que es menor que el promedio de células, pueden ser descartados y no mirar allí. Por el contrario, si es inferior a la media – entre esos números a la derecha, no se puede buscar. A continuación, seleccione una nueva zona de búsqueda, donde el primer elemento será el elemento central de toda la matriz, y el último y el último voluntad. El número medio de nuevo campo será ¼ de todo el segmento, es decir, (el último elemento + el elemento de medio de toda la matriz) / 2. Una vez más, la misma operación se lleva a cabo – una comparación con el número medio de la matriz. Si el valor objetivo es inferior a la media, rechazamos el lado derecho, y también para hacer a continuación, hasta ahora no se desea este elemento medio.

Por supuesto, lo mejor es mirar un ejemplo de la forma de escribir de búsqueda binaria. Pascal aquí será adaptarse a cualquier persona – versión no es importante. Vamos a escribir un programa sencillo.

Es una matriz de 1 a h bajo el nombre "massiv", una variable que indica el límite inferior de la búsqueda, llamado "niz", el límite superior, llamado "verh", el promedio término de búsqueda – "sredn"; y el número necesario – "ISK".

Por lo tanto, primero asignamos el límite superior e inferior del rango de búsqueda:

niz: = 1;
verh: = h + 1;

A continuación, organizar el ciclo de "hasta que la parte inferior es menor que el límite superior":

Mientras niz <verh – 1 hacer
empezar

En cada paso, se divide el segmento 2:

sredn: = (niz + verh) div 2; {Utilice el div función, ya que el resto se dividen sin}

Cada momento de la revisión. Debido a que el objeto ya se ha encontrado si se desea el medio, ciclo de interrupción:

іf sredn = ISK luego romper;

Si el elemento medio de la matriz más de lo deseado, desechar el lado izquierdo, es decir, el límite superior de la media elemento nombrar:

si MASSIV [sredn]> ISK entonces verh: = sredn;

Y si por el contrario, hace que el límite inferior:

más niz: = sredn;
terminar;

Eso es todo lo que será en el programa.

Vamos a considerar cómo se verá el método binario en la práctica. Considere esta matriz: 1, 3, 5, 7, 10, 12, 18 y que buscará el número 12.

En total tenemos 7 elementos, también lo hará el cuarto medio, el valor 7.

1 3 5 7 10 12 18

Desde hace más de 12, 7, 1.3 y 5 elementos, podemos descartar. Entonces tenemos el número 4, 4/2 ningún residuo es 2. Por lo tanto, un nuevo elemento será un promedio de 10.

7 10 12 18

Dado que 12 es mayor que 10, descartamos 7. sigue siendo sólo el 10, 12 y 18.

En este caso, el elemento central es ya de 12, que es el número requerido. Esta tarea se ha completado – Número 12 encontrado.