Informatică Algoritmi
Metode de cautare binara explicatii
Căutarea binară este un algoritm eficient pentru găsirea unui element într-o listă sortată. Funcționează prin împărțirea repetată a intervalului de căutare la jumătate. Este mult mai rapidă decât căutarea secvențială pentru liste mari.
Pași algoritmului
- 1 Pasul 1 Stabilește limitele intervalului: stânga = 0, dreapta = lungimea listei - 1.
- 2 Pasul 2 Calculează mijlocul: mijloc = (stânga + dreapta) / 2 (parte întreagă).
- 3 Pasul 3 Compară elementul de la poziția mijloc cu valoarea căutată.
- 4 Pasul 4 Dacă sunt egale, returnează poziția mijloc. Dacă valoarea căutată este mai mică, actualizează dreapta = mijloc - 1. Dacă este mai mare, actualizează stânga = mijloc + 1.
- 5 Pasul 5 Repetă pașii 2-4 până când stânga > dreapta (elementul nu există).
Exemplu numeric
- Lista Fie lista sortată [2, 5, 8, 12, 16, 23, 38, 56] și valoarea căutată 23.
- Iterația 1 stânga=0, dreapta=7, mijloc=3 (valoarea 12). 23 > 12, deci stânga devine 4.
- Iterația 2 stânga=4, dreapta=7, mijloc=5 (valoarea 23). Găsit la poziția 5.
Folosește căutarea binară doar pentru liste sortate, altfel nu funcționează corect.