Informatică Algoritmi
Algoritmi de cautare binara exemple
Căutarea binară este un algoritm eficient de găsire a unui element într-o listă sortată, cu complexitate O(log n). Funcționează prin împărțirea repetată a intervalului de căutare la jumătate, comparând elementul țintă cu cel din mijloc. Reduce drastic timpul față de căutarea liniară.
Pașii algoritmului
- 1 Pasul 1 Definești limitele intervalului: stânga = 0, dreapta = lungimea listei - 1.
- 2 Pasul 2 Calculezi mijlocul: mijloc = (stânga + dreapta) // 2.
- 3 Pasul 3 Compari elementul de la mijloc cu ținta: dacă sunt egale, returnezi poziția.
- 4 Pasul 4 Dacă ținta este mai mică, actualizezi dreapta = mijloc - 1; dacă este mai mare, stânga = mijloc + 1.
- 5 Pasul 5 Repeti pașii până când stânga > dreapta, indicând că elementul nu există.
Exemplu numeric
- Lista sortată [2, 5, 8, 12, 16, 23, 38, 56]
- Căutăm 23 Mijloc = (0+7)//2 = 3 → element 12 < 23 → stânga = 4.
- Iterația 2 Mijloc = (4+7)//2 = 5 → element 23 = 23 → găsit la poziția 5.
- Căutăm 10 Mijloc = 3 → 12 > 10 → dreapta = 2; mijloc = (0+2)//2 = 1 → 5 < 10 → stânga = 2; mijloc = (2+2)//2 = 2 → 8 < 10 → stânga = 3 > dreapta → nu există.
Verifică întotdeauna că lista este sortată înainte de a aplica căutarea binară, altfel algoritmul nu funcționează.