Informatică Programare
Cautare binara C++ explicata
Căutarea binară este un algoritm eficient de găsire a unui element într-o listă sortată, cu complexitate O(log n). În C++, funcționează prin împărțirea repetată a intervalului de căutare la jumătate, comparând elementul țintă cu elementul din mijloc și eliminând jumătatea în care ținta nu poate fi. Este mult mai rapidă decât căutarea liniară pentru liste mari.
Pași algoritmului de căutare binară
- 1 Verifică sortarea Asigură-te că lista este sortată în ordine crescătoare; altfel, algoritmul nu funcționează.
- 2 Stabilește limitele Setăm low la începutul listei (index 0) și high la sfârșit (index n-1).
- 3 Calculează mijlocul mid = low + (high - low) / 2; evită overflow comparativ cu (low+high)/2.
- 4 Compară cu ținta Dacă arr[mid] == target, returnează mid. Dacă arr[mid] < target, actualizează low = mid + 1; altfel, high = mid - 1.
- 5 Repetă sau termină Repetă pașii până când low > high, indicând că elementul nu a fost găsit.
Exemplu de implementare C++
- Funcția binarySearch int binarySearch(int arr[], int n, int target) { int low = 0, high = n-1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) low = mid + 1; else high = mid - 1; } return -1; }
- Vector de intrare int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; int n = 10; int target = 23;
- Apelul funcției int result = binarySearch(arr, n, target);
- Rezultat result este 5, deoarece 23 se află la indexul 5 în vector.
Folosește căutarea binară doar pe liste sortate; pentru liste nesortate, sortează-le mai întâi sau folosește căutarea liniară.