Informatică Algoritmi
Algoritmi de cautare binara explicatii detaliate
Căutarea binară este un algoritm eficient pentru găsirea unui element într-o listă sortată, reducând spațiul de căutare la jumătate la fiecare pas. Ea are complexitatea O(log n), mult mai rapidă decât căutarea liniară. Algoritmul funcționează prin compararea elementului țintă cu elementul din mijlocul listei.
Pașii algoritmului
- 1 Pasul 1 Definești indicii stânga = 0 și dreapta = n-1, unde n este lungimea listei sortate.
- 2 Pasul 2 Calculezi mijloc = (stânga + dreapta) // 2. Compari elementul de la mijloc cu ținta.
- 3 Pasul 3 Dacă ținta este mai mică, actualizezi dreapta = mijloc - 1. Dacă este mai mare, stânga = mijloc + 1. Repeti până când găsești ținta sau stânga > dreapta.
Exemplu detaliat
- Lista și ținta Lista sortată: [2, 5, 8, 12, 16], n=5. Ținta: 12.
- Iterația 1 stânga=0, dreapta=4, mijloc=2 (element 8). 12 > 8, deci stânga devine 3.
- Iterația 2 stânga=3, dreapta=4, mijloc=3 (element 12). Găsit la index 3.
- Număr de pași Pentru n=5, căutarea binară necesită cel mult log2(5) ≈ 3 pași, față de 5 pentru căutarea liniară.
Asigură-te că lista este sortată înainte de a aplica căutarea binară, altfel algoritmul nu funcționează.