binary search (tsz. binary searches)
A bináris keresés egy hatékony keresési algoritmus, amelyet rendezett tömbökben vagy listákban használnak egy adott elem megkeresésére. Az algoritmus lényege, hogy minden lépésben felezi a keresési területet, így jelentősen gyorsabb, mint a lineáris keresés.
A bináris keresés alapötlete a következő: 1. Kezdeti feltételezés: A keresett elem egy rendezett tömbben található. 2. Középső elem kiválasztása: Megvizsgáljuk a tömb közepén lévő elemet. 3. Döntés: - Ha a középső elem megegyezik a keresett elemmel, akkor megtaláltuk. - Ha a keresett elem kisebb, mint a középső, akkor a keresést a tömb bal felében folytatjuk. - Ha a keresett elem nagyobb, mint a középső, akkor a keresést a tömb jobb felében folytatjuk. 4. Ismétlés: A folyamatot addig ismételjük, amíg meg nem találjuk az elemet, vagy a keresési tartomány ki nem merül.
A bináris keresés legrosszabb esetben O(log n) időbonyolultságú, ami sokkal gyorsabb, mint a lineáris keresés O(n) időbonyolultsága.
Az iteratív változatnál egy ciklus segítségével hajtjuk végre a keresést.
#include <iostream>
using namespace std;
int binarisKereses(int tomb, int meret, int keresett) {
int bal = 0, jobb = meret - 1;
while (bal <= jobb) {
int kozep = bal + (jobb - bal) / 2;
// Ha megtaláltuk
if (tomb == keresett)
return kozep;
// Ha a keresett elem kisebb, a bal oldalon folytatjuk
if (tomb > keresett)
jobb = kozep - 1;
else
// Ha nagyobb, a jobb oldalon folytatjuk
bal = kozep + 1;
}
return -1; // Ha nem található
}
int main() {
int tomb = {2, 3, 4, 10, 40};
int meret = sizeof(tomb) / sizeof(tomb);
int keresett = 10;
int eredmeny = binarisKereses(tomb, meret, keresett);
if (eredmeny != -1)
cout << "Elem megtalálva az indexen: " << eredmeny << endl;
else
cout << "Elem nincs a tömbben." << endl;
return 0;
}
A bináris keresés rekurzív módon is megvalósítható, ahol a keresési tartományt egy rekurzív függvényhívás szűkíti.
#include <iostream>
using namespace std;
int binarisKeresesRekurziv(int tomb, int bal, int jobb, int keresett) {
if (bal <= jobb) {
int kozep = bal + (jobb - bal) / 2;
// Ha megtaláltuk
if (tomb == keresett)
return kozep;
// Ha a keresett kisebb, a bal oldali tartományban keresünk
if (tomb > keresett)
return binarisKeresesRekurziv(tomb, bal, kozep - 1, keresett);
// Ha a keresett nagyobb, a jobb oldali tartományban keresünk
return binarisKeresesRekurziv(tomb, kozep + 1, jobb, keresett);
}
return -1; // Ha nem található
}
int main() {
int tomb = {2, 3, 4, 10, 40};
int meret = sizeof(tomb) / sizeof(tomb);
int keresett = 10;
int eredmeny = binarisKeresesRekurziv(tomb, 0, meret - 1, keresett);
if (eredmeny != -1)
cout << "Elem megtalálva az indexen: " << eredmeny << endl;
else
cout << "Elem nincs a tömbben." << endl;
return 0;
}
| Eset | Időbonyolultság |
|---|---|
| Legjobb eset | O(1) (ha elsőre megtaláljuk) |
| Átlagos eset | O(log n) |
| Legrosszabb eset | O(log n) |
A logaritmikus időbonyolultság miatt a bináris keresés sokkal gyorsabb, mint a lineáris keresés. Például: - Egy 1 000 000 elemű tömbben a lineáris keresés akár 1 000 000 lépést is igényelhet. - A bináris keresés legrosszabb esetben log₂(1 000 000) ≈ 20 lépés alatt végez.
A bináris keresés egy rendkívül hatékony algoritmus, amely rendezett tömbökben használható. Az iteratív és rekurzív változatok egyaránt gyorsabbak, mint a hagyományos lineáris keresés.
✅ Nagyon gyors (O(log n))
✅ Könnyen implementálható
✅ Iteratív és rekurzív módon is működik
❌ Csak rendezett adatszerkezetekben használható
❌ Rekurzív változat esetén nagy adathalmazoknál stack overflow léphet fel