Căutarea binară - explicarea algoritmului în c++

În curs de dezvoltare software array-urile sunt folosite peste tot. "Tipuri de date inteligente în software-ul modern limbaje de programare, Ca de exemplu, array-urile dinamice oferă mari oportunități de a lucra cu obiecte într-un mod convenabil. Dar algoritmii din spatele acestor tipuri de date au fost dezvoltați în primele zile ale informaticii, la mijlocul secolului XX. Primul algoritm de căutare binară a fost publicat în 1946.

Luați în considerare cei mai populari algoritmi să lucreze cu array-uri.

Căutare secvențială (liniară)

Acesta este cel mai simplu algoritm pentru a găsi o valoare într-un array. Utilizează o metodă pentru a compara elementele tabloului, unul câte unul, cu valoarea cheii. De obicei, se face de la stânga la dreapta. Se utilizează atunci când există puține elemente într-o matrice sau când lista nu este ordonată. Total ineficientă în matrici mari, unde căutarea binară este folosită în mod obișnuit. Algoritmul funcționează după cum urmează:

• Comparăm valoarea cheii cu valoarea elementului a matricei .
• Dacă valorile sunt egale, returnăm valoarea.
• Dacă nu - creșteți valoarea variabilei buclei cu unu și comparați-o cu următorul element al matricei.

Căutarea secvențială a indexului

O modalitate mai eficientă de a găsi o valoare într-un array sortat. Dar este mai solicitantă în ceea ce privește resursele.

Căutare binară

Căutarea binară este un algoritm pentru găsirea unui element într-un tablou prin împărțirea consecutivă a tabloului în două și compararea numărului original cu numărul din mijlocul tabloului. Dacă numărul din mijloc este mai mic decât valoarea pe care o căutăm, căutăm mai departe în a doua parte; dacă este mai mare, continuăm căutarea în prima parte. Acest algoritm este cel mai rapid dintre toți și funcționează după cum urmează:

• Găsiți mai întâi valoarea obiectului din mijlocul matricei. Verificați-o în raport cu valoarea inițială.
• Dacă valoarea din mijloc este mai mică decât valoarea inițială, continuați căutarea în a doua jumătate, dacă este mai mare, căutați în prima jumătate.
• În jumătatea rezultată, faceți același lucru: împărțiți-o la jumătate și comparați valoarea rezultată.

Această căutare este efectuată până când valoarea inițială este egală cu valoarea din matrice. Dacă acest lucru nu se întâmplă, înseamnă că această valoare nu există în matrice.

Există câteva capcane care pot fi întâlnite atunci când se proiectează o căutare binară.

Depășirea tipului de date selectat

Pentru a găsi valoarea din mijlocul matricei, adunați valorile din dreapta și din stânga și împărțiți-le la doi. Asta este:

Mijlocul matricei = valoarea din stânga + (valoarea din stânga - valoarea din dreapta)/2

Există pericolul unei depășiri a tipului de date în timpul unei operații de adunare. În cazul în care un array conține valori de dimensiuni atât de mari, trebuie să folosim diverse trucuri pentru a evita riscul de. Mai jos sunt câteva erori standard în proiectarea unei căutări binare.

Erori de valoare

Sau o eroare. Este foarte important să luați în considerare următoarele opțiuni:

• Matrice goală.
• Nicio valoare.
• Supraîncărcare matrice.

Mai multe instanțe

Rețineți că, dacă există mai multe exemple identice de chei în matrice, programul trebuie să găsească o anumită cheie (prima, ultima, următoarea).

Să ne uităm la o implementare a acestui algoritm în limbajul de programare C plus. Rețineți că căutarea binară funcționează numai cu un tablou sortat! Dacă array-ul nu este sortat mai întâi, rezultatul calculelor va fi incorect.

Aici este codul C ++. În primul rând, se inițializează un tablou de variabile întregi, arr, de mărimea zece, care are o dimensiune de zece. În continuare, operatorul cin din bucla for așteaptă ca utilizatorul să introducă zece valori (linia zece).

La linia 20, programul așteaptă ca utilizatorul să introducă valoarea cheii.

Liniile 29 - 35 reprezintă o implementare a algoritmului de căutare binară. Execuția programului scrie valoarea elementului din mijloc în variabila mid folosind formula:

Array middle (mid) = (Valoarea din stânga (l) + Valoarea din dreapta (r))/2

Șirul

arr[mid]==key

Se verifică dacă valoarea mediană este egală cu valoarea cheie. Dacă este egală, atunci variabila indicator este schimbată la TRUE, adică problema este rezolvată.

Dacă valoarea din mijloc este mai mare decât valoarea cheii noastre, atunci părții din dreapta (variabila r) i se atribuie mijlocul. Dacă este invers, mijlocul este plasat în r.

Aceasta din urmă este o verificare a variabilei booleene flag.

Avantajele căutării binare

Căutarea binară trebuie folosită dacă doriți ca programul să funcționeze rapid. Și pentru a scrie un astfel de algoritm nu este dificil chiar și pentru un programator începător. Dar este foarte important să se ia în considerare toate cazurile extreme: depășiri de matrice, valoare lipsă, eroare de depășire a datelor.

Dezavantaje

Pentru ca algoritmul să funcționeze corect, matricea trebuie mai întâi să fie sortată. Pentru a face acest lucru, puteți utiliza funcția sort() din limbajul de programare C++. Și încă un aspect important care trebuie subliniat ia aminte, învățare C și C căutare binară C++. Acest algoritm poate fi utilizat numai cu anumite structuri de date. De exemplu, structurile care utilizează liste legate nu se vor potrivi aici.