Busca binaria - unha das formas máis fáciles de atopar un elemento nunha matriz

Moitas veces, os desenvolvedores, mesmo os principiantes, confrontado co feito de que hai un conxunto de números, que debe atopar un número específico. É esta colección é chamado un array. E para atopar elementos nel, hai unha infinidade de formas. Pero o máis simple deles pode ser considerado unha busca binaria á dereita. Que é a rede é? E como aplicar busca binaria? Pascal é o ambiente máis doado para a organización dun programa deste tipo, polo que imos usalo para estudar.

En primeiro lugar, analizar cales son as vantaxes deste método, é para que poidamos comprender, o que é o punto no estudo do tema. Entón, imos ter un array cunha dimensión de polo menos 100000000 elementos, que precisan atopar algunha. Por suposto, este problema pode ser facilmente resolto por unha busca lineal simple, en que estamos usando o ciclo pode comparar o elemento necesario con todos os que están na matriz. O problema é que a posta en marcha desta idea vai levar moito tempo. Nun programa Pascal simple en varios tratamentos e tres liñas do texto principal, non vai notar iso, pero cando chegamos a un máis ou menos grandes proxectos con un gran número de axencias e boa función, o programa estará listo para ser cargado por moito tempo. Sobre todo se o ordenador é un feble desempeño. Polo tanto, hai unha busca binaria, o que reduce o tempo de procura polo menos dúas veces.

Entón, cal é o principio de funcionamento deste método? Inmediatamente debe dicir que busca binaria funciona non é en calquera array, pero só nun conxunto ordenado de números. En cada paso dado elemento do medio da matriz (ou sexa, o número do elemento). Se o requirido número é maior que a media, entón todo o que queda, que é menos que a célula media, pode ser descartado e non mirar para alí. Pola contra, se inferior á media - entre os números á dereita, non pode buscar. A continuación, seleccione unha nova área de investigación, onde o primeiro elemento a elemento medio de toda a matriz, ea última ea última vontade. O número medio de novo campo será ¼ de todo o segmento, que é, (o último elemento + o elemento do medio de toda a matriz) / 2. Unha vez máis, a mesma operación é realizada - unha comparación co número medio da matriz. Se o valor obxectivo é inferior á media, rexeitamos o lado dereito, e tamén para facer a continuación, ata agora este elemento central non desexado.

Por suposto, é mellor mirar para un exemplo de como escribir busca binaria. Pascal aquí debería atender a ninguén - versión non é importante. Imos escribir un programa sinxelo.

El é unha matriz de 1 a h baixo o nome "massiv", unha variable que indica o límite inferior da investigación, chamado "niz", o límite superior, chamada "verh", o prazo medio de investigación - "sredn"; eo número necesario - "isco".

Entón, primeiro imos asignar o límite superior e inferior do rango de procura:

niz: = 1;
verh: = H 1;

Logo organizar o ciclo "ata que o fondo é menor que o límite superior":

Mentres niz comezar

A cada paso, dividimos o segmento 2:

sredn: div 2 = (+ niz verh); {Use a función div porque a división sen restante}

Cada momento da revisión. Xa que o produto xa foi atopada o medio desexado, interromper ciclo:

іf sredn = ISK entón romper;

Se o elemento do medio da matriz máis que o desexe, descartar o lado esquerdo, é dicir, o límite superior da media nomear elemento:

se massiv [sredn]> ISK entón verh: = sredn;

E se, pola contra, fai o límite inferior:

outra niz: = sredn;
acabar;

Isto é todo o que vai estar no programa.

Imos considerar como se ve o método binario na práctica. Considero esta matriz: 1, 3, 5, 7, 10, 12, 18 e que vai buscar o número 12.

En total, ten 7 elementos, así que a cuarta forma, o valor de 7.

Desde máis de 12, 7, 1,3 e 5 elementos, podemos descartar. Entón temos o número 4, 4/2 ningún residuo é 2. Así, un novo elemento será unha media de 10.

Desde 12 é maior que 10, descartamos 7. permanece só 10, 12 e 18.

Aquí, o elemento do medio xa é 12, é o número necesario. Esta tarefa é rematada - número 12 atopados.