Atunci când căutarea unui element trebuie efectuată într-o ordine ascendentă sau descendentă ordonată, vom folosi algoritmul de căutare binar. Metoda folosește o strategie „divide et impera“, și anume, o anumită secvență este împărțită în două părți egale, iar căutarea este efectuată într-una din aceste părți, care este apoi de asemenea împărțită în două, și așa mai departe până când elementul dorit pentru a detecta prezența sau lipsa acestora. Folosiți această operație, reducând de fiecare dată căutarea zonei de două ori, este permisă numai pe baza faptului că elementele secvenței sunt pre-ordonate. Găsirea elementul de mijloc (pentru a face acest lucru, știind numărul de elemente de matrice nu va fi dificil), și comparând-o cu valoarea dorită, puteți fi sigur de a spune, în cazul în care există un element necesar în raport cu elementul de mijloc.
Apoi, vom presupune că elementele matricei sunt aranjate în ordine ascendentă, deoarece nu există nici o diferență semnificativă în ceea ce privește modul în care sunt ordonate: în ordine ascendentă sau descendentă. De asemenea, indicăm limitele zonei de căutare prin elementele stânga și dreapta - stânga și dreapta.
Progresul algoritmului, împărțit în etape, este după cum urmează:
- zona de căutare (în primul pas este întreaga matrice) să se împartă în două părți egale, prin determinarea elementului său de mijloc (mijloc);
- elementul mediu este comparat cu cel cerut (cheie), rezultatul acestei comparații va fi unul din cele trei cazuri:
- cheie
- cheie> mijloc. Limita stângă a zonei de căutare este lângă elementul intermediar (stânga ← mijloc + 1);
- cheie = mijloc. Valorile elementelor medii și necesare sunt aceleași, deci elementul este găsit, lucrarea algoritmului este finalizată.
- cheie
- dacă nu există un singur element rămas pentru verificare, algoritmul se termină, altfel se efectuează trecerea la pasul 1.
Tabelul de mai jos arată o anumită matrice integeră și o implementare pas cu pas a algoritmului de căutare binară pentru elementele sale. Pentru a economisi spațiu în tabel, stânga, dreapta și mijlocul sunt înlocuite cu a, b și c.
Există o secvență de numere întregi aranjate în ordine crescătoare, iar cheia - 16. Inițial, numărul de elemente de frontieră sunt elemente cu numerele 1 și 9, și valorile 1 și 81. Numărul de celule mediu Calculați, care folosește, de obicei cu formula (dreapta + stânga) / 2 sau stânga + (dreapta-stânga) / 2 (în programe se va utiliza cea de-a doua formulă, cea mai stabilă de depășire). După comparație, rezultă că elementul cerut este mai mic decât media și, prin urmare, căutarea ulterioară este efectuată în partea stângă a secvenței. Algoritmul continuă să fie realizat într-un mod similar, până când se găsește la pasul 4 al elementului dorit.
Este demn de remarcat faptul că acest lucru va necesita mult mai puțin timp decât în cazul în care ne-am folosit de căutare liniară, dar spre deosebire de căutare binare liniare funcționează doar cu matrice ale căror elemente sunt ordonate, care, fără îndoială, le conferă o specificitate negativă.
Codul programului C ++:
#include "stdafx.h"
#include
folosind namespace std;
const int N = 10;
// căutare binară
int BinarySearch # 40; int A # 91; # 93;. int cheie # 41;
# 123;
int stânga = 0. dreapta = N, mijloc;
în timp ce # 40; stânga <= right )
# 123;
mijloc = stânga + # 40; dreapta - stânga # 41; / 2;
dacă # 40; cheie altfel dacă # 40; cheie> A # 91; la mijlocul # 93; # 41; stânga = mijloc + 1;
altceva returnează mijlocul;
# 125;
întoarcere - 1;
# 125;
// funcția principală
void principal # 40; # 41;
# 123;
setlocale # 40; LC_ALL, "Rus" # 41; ;
int i, cheie;
int A # 91; N # 93; ;
cout <<"Искомый элемент> "tasta cin >>; introduceți cheia
cout <<"Исходный массив: " ;
pentru # 40; i = 0; eu
altfel cout <<" \n Номер элемента: " <
# 125;
Codul programului pe Pascal:
program BinSearch;
utilizează CRT;
const N = 10;
tip Arr = matrice # 91; 1. N # 93; de intreg;
var mediu. la stânga. dreapta. cheie. i. întreg;
A. Arr;
funcția BinarySearch # 40; A. Arr; cheie. întreg # 41;. întreg;
începe
stânga: = 1; dreapta: = N;
în timp ce este lăsat<= right do
începe
mijloc: = stânga + # 40; dreapta - stânga # 41; div 2;
dacă # 40; cheie altfel dacă # 40; cheie> A # 91; la mijlocul # 93; # 41; apoi stânga: = mijloc + 1
altceva începe BinarySearch: = mijloc; ieșire; se încheie;
se încheie;
BinarySearch: = - 1;
se încheie;
începe
scrie # 40; 'Element de căutare' # 41; ; citit # 40; cheie # 41; ;
scrie # 40; "Matricea sursă:" # 41; ;
pentru i: = 1 la N face
începe A # 91; eu # 93; : = N * i; scrie # 40; A # 91; eu # 93;. „“ # 41; ; se încheie;
writeln;
dacă # 40; binarySearch # 40; A. cheie # 41; = - 1 # 41; apoi scrieți # 40; "Elementul nu a fost găsit" # 41;
scrie altfel # 40; "Numărul elementului:". binarySearch # 40; A. cheie # 41; # 41; ;
end.
Programul poate fi implementat în prezența unei game largi de elemente de testare, dar cum este umplut, indiferent de utilizator, o sumă fixă de valori constante, poate fi inutilă.
În cazul în care prima valoare mijlocul coincide cu o cheie, atunci se consideră că algoritmul a executat pentru cel mai bun O sa timp (1). În cel mai rău și cel mai rău caz, timpul de funcționare al algoritmului este O (logn), care este mult mai rapid decât căutarea liniară, necesitând un timp liniar.