Molto spesso i programmatori, anche principianti,si trovano di fronte al fatto che esiste un insieme di numeri in cui è necessario trovare un certo numero. Questa raccolta è chiamata array. E per trovare l'elemento desiderato in esso, ci sono molti modi. Ma la più semplice tra queste può essere giustamente considerata una ricerca binaria. Qual è questo metodo? E come si implementa la ricerca binaria? Pascal è l'ambiente più semplice per organizzare un programma del genere, quindi lo useremo per studiare.
Innanzitutto, analizzeremo quali sono i vantaggi di questo metodo, perché in questo modo possiamo capire
Quindi, qual è il principio di funzionamento di questo?metodo? Va detto subito che la ricerca binaria non funziona in nessun array, ma solo in un insieme ordinato di numeri. Ad ogni passaggio successivo, viene preso l'elemento centrale dell'array (ovvero il numero dell'elemento). Se il numero desiderato è maggiore della media, tutto ciò che si trova a sinistra, ovvero inferiore all'elemento centrale, può essere scartato e non cercato lì. E viceversa, se è inferiore alla media - tra quei numeri a destra, non è necessario cercare. Successivamente, selezioniamo una nuova area di ricerca, dove il primo elemento sarà l'elemento centrale dell'intero array e l'ultimo rimarrà l'ultimo. Il numero medio della nuova area sarà ¼ dell'intero segmento, cioè (l'ultimo elemento + l'elemento centrale dell'intero array) / 2. Ancora una volta, viene eseguita la stessa operazione: confronto con la media dell'array. Se il valore desiderato è inferiore alla media, scartiamo il lato destro e facciamo lo stesso ulteriormente, fino a quando questo elemento centrale risulta essere quello desiderato.
Naturalmente, è meglio guardare un esempio di come viene scritta la ricerca binaria. Qualsiasi Pascal funzionerà qui - la versione non è importante. Scriviamo un semplice programma.
Conterrà un array da 1 a h chiamato"massiv", variabile che indica il limite inferiore della ricerca denominato "niz", il limite superiore denominato "verh", il termine di ricerca centrale denominato "sredn"; e il numero richiesto è "isk".
Quindi, per prima cosa assegniamo i limiti superiore e inferiore dell'intervallo di ricerca:
niz: = 1;
verh: = h + 1;
Quindi organizziamo il ciclo "mentre il limite inferiore è inferiore al limite superiore":
Mentre niz <verh - 1 do
inizio
Ad ogni passaggio, dividiamo il segmento per 2:
sredn: = (niz + verh) div 2; {usa la funzione div perché dividiamo senza resto}
Ogni volta che controlliamo. Se la media è uguale a quella desiderata, interrompiamo il ciclo, poiché l'elemento richiesto è già stato trovato:
se sredn = isk allora interrompi;
Se l'elemento centrale dell'array è più grande di quello desiderato, scartare il lato sinistro, ovvero assegnare l'elemento centrale come bordo superiore:
se massiv [sredn]> isk allora verh: = sredn;
E se al contrario, lo rendiamo il limite inferiore:
else niz: = sredn;
fine;
Questo è tutto ciò che sarà nel programma.
Vediamo come apparirà in pratica il metodo binario. Prendiamo un array come questo: 1, 3, 5, 7, 10, 12, 18 e cerchiamo il numero 12 in esso.
In totale, abbiamo 7 elementi, quindi quello centrale sarà il quarto, il suo valore è 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Poiché 12 è maggiore di 7, possiamo scartare gli elementi 1,3 e 5. Quindi ci rimangono 4 numeri, 4/2 senza resto è 2. Quindi, il nuovo elemento centrale sarà 10.
| 7 | 10 | 12 | 18 |
Qui l'elemento centrale è già 12, questo è il numero desiderato. Compito completato - numero 12 trovato.
