Informatică Algoritmi
Cautare binara algoritm explicatie
Căutarea binară este un algoritm eficient pentru găsirea unui element într-o listă sortată, prin înjumătățirea repetată a intervalului de căutare. Complexitatea sa este O(log n), mult mai rapidă decât căutarea liniară. Funcționează doar pe liste ordonate.
Pașii algoritmului
- 1 Pasul 1 Definește limitele intervalului: stânga = 0, dreapta = lungimea listei - 1.
- 2 Pasul 2 Calculează mijlocul: mijloc = (stânga + dreapta) // 2.
- 3 Pasul 3 Compară elementul de la mijloc cu cel căutat. Dacă sunt egale, returnează poziția.
- 4 Pasul 4 Dacă elementul căutat este mai mic, actualizează dreapta = mijloc - 1; altfel, stânga = mijloc + 1.
- 5 Pasul 5 Repetă pașii 2-4 până când stânga > dreapta, indicând că elementul nu există.
Exemplu numeric
- Lista inițială [2, 5, 8, 12, 16, 23, 38, 56], căutăm 23.
- Prima iterație Mijloc = (0+7)//2 = 3, elementul 12 < 23, deci stânga devine 4.
- A doua iterație Mijloc = (4+7)//2 = 5, elementul 23 = 23, găsit la poziția 5.
Verifică întotdeauna că lista este sortată înainte de a aplica căutarea binară.