Pentru ce este folosit algoritmul de căutare binară?

Pentru a căuta eficient un element într-un array sortat.

Esenta constă în compararea valorii căutate cu elementul din mijlocul intervalului de căutare curent. Dacă sunt egale, elementul a fost găsit. Dacă valoarea căutată este mai mică, căutarea se restrânge la jumătatea stângă; dacă este mai mare, la jumătatea dreaptă. Procesul se repetă până când elementul este găsit sau intervalul de căutare devine gol.

Avantajul față de căutarea liniară este complexitatea temporală logaritmică, O(log n), în timp ce pentru căutarea liniară este O(n). Acest lucru o face mult mai rapidă pentru array-uri mari.

Aplicații:

• Căutare în dicționare și baze de date (indici).
• Algoritmi de sortare (de exemplu, în merge sort).
• Căutarea elementului rădăcină al unei ecuații.
• Căutare în structuri de date de tip copaci B.