Căutare binară (binară)

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ă:

1. 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);
2. 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ă.
3. 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 # 123; A # 91; eu # 93; = N * i; cout < dacă # 40; binarySearch # 40; A, cheie # 41; == - 1 # 41; cout <<" \n Элемент не найден" ;
altfel cout <<" \n Номер элемента: " < sistem # 40; "pauză >> vid" # 41; ;
# 125;

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.

• Căutarea binară este una dintre cele mai simple căi de a găsi un element dintr-o matrice

• Cum se înregistrează ip - cum se înregistrează rapid o căutare IP de locuri de muncă

• Cum de a face Google răspunsul implicit aici!

Trimiteți-le prietenilor: