Informatică Algoritmi
Exercitii rezolvate algoritmi de cautare binara
Căutarea binară este un algoritm eficient care găsește un element într-o listă sortată, prin împărțirea repetată a intervalului de căutare la jumătate. Se rezolvă exerciții aplicând pașii algoritmului pe liste numerice. De exemplu, în lista [1, 3, 5, 7, 9], căutând 5, algoritmul o găsește în doi pași.
Exercițiu 1: Căutare cu succes
- 1 Enunț Găsește valoarea 8 în lista sortată [2, 4, 6, 8, 10, 12, 14].
- 2 Pasul 1: Setează limitele Stânga = 0 (primul element), dreapta = 6 (ultimul element).
- 3 Pasul 2: Calculează mijlocul Mijloc = (0+6)/2 = 3 (index). Elementul la index 3 este 8.
- 4 Pasul 3: Compară și găsește 8 este egal cu valoarea căutată, deci algoritmul se oprește și returnează indexul 3.
Exercițiu 2: Căutare fără succes
- Enunț Caută valoarea 5 în lista [1, 3, 7, 9, 11].
- Pașii de rezolvare Stânga=0, dreapta=4; mijloc=2 (element 7). 5<7, deci dreapta devine 1; mijloc=0 (element 1). 5>1, stânga devine 1; mijloc=1 (element 3). 5>3, stânga devine 2; stânga>dreapta, deci 5 nu există.
- Rezultat Algoritmul returnează -1 sau un mesaj că valoarea nu a fost găsită.
Exersează cu liste de diferite dimensiuni pentru a înțelege cum numărul de pași crește logaritmic.