Bináris keresés

Elemek keresése tömbben

1. szekvenciális keresés

Megnézzük a tömb minden elemét rendre, eldöntjük, hogy az aktuális elem olyan-e, mint amit keresünk.

Példa: Adott n, majd egy n elemű tömb. Ha megvan benne a 100, akkor írjuk ki, hogy “megvan”, különben azt, hogy “nincs”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream be("input.txt");

    int n;
    be >> n;

    int t[1000];

    for (int i = 0; i < n; i++)
        be >> t[i];

    // keresés
    bool van = false;

    for (int i = 0; i < n; i++)
        if (t[i] == 100)
            van = true;

    if (van) {
        cout << "megvan" << endl;
    }
    else {
        cout << "nincs" << endl;
    }

    return 0;
}

2. bináris keresés rendezett tömbben

Minden lépésben megnézzük annak a tartománynak a közepét, ahol zajlik a keresés. Annak függvényében, hogy ott milyen érték van, vagy csak ettől balra vagy csak ettől jobbra érdemes folytatni a keresést.

Példa: Adott n, majd n elemű növekvő sorrendbe rendezett tömb, illetve adott még egy x érték. El kell dönteni minél kevesebb összehasonlítással, hogy az x érték megjelenik-e a sorozatban! (kiírjuk, hogy “igen” vagy “nem”)

    Pl. bemenet:
        7
        1 4 6 6 8 10 15
        9

        kimenet: nincs

        a[i]: 1 4 6 6 8 10 15
           i: 0 1 2 3 4 5  6
              b     ^      j
                    k

        a[i]: 1 4 6 6 8 10 15
           i: 0 1 2 3 4 5  6
                    ^ b    j

        a[i]: 1 4 6 6 8 10 15
           i: 0 1 2 3 4 5  6
                      b ^  j
                        k

        a[i]: 1 4 6 6 8 10 15
           i: 0 1 2 3 4 5  6
                      bj

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream be("input.txt");

    int n;
    be >> n;

    int t[1000];

    for (int i = 0; i < n; i++)
        be >> t[i];

    int x; // keresett elem
    be >> x;

    int bal = 0;
    int jobb = n-1;

    bool van = false;

    while (bal <= jobb && !van) {
        int kozep = (bal+jobb) / 2;

        cout << "megnez t[" << kozep <<
            "] = " << t[kozep] << endl;

        if (t[kozep] == x)
            van = true;
        else if (t[kozep] < x)
            bal = kozep+1;
        else // >
            jobb = kozep-1;
    }

    if (van)
        cout << "megvan" << endl;
    else
        cout << "nincs" << endl;

    return 0;
}

Gyakorlatok

Érettségi 2024 augusztus, II.2

Egy 7 elemű tömbben bináris kereséssel keressük az x=16 értéket. A 2, 10 és 24 számok elemei a tömbnek. Írjuk le a tömb egy lehetséges állapotát (az értékek felsorolásával) ahhoz, hogy az x pontosan két elemmel legyen összehasonlítva az algoritmus futása során!

Megoldás:

A középső elem nem lehet 16, de a következő (bal vagy jobb oldali részben a középső) már mindenképp 16 kell legyen, hogy ne történjenek további összehasonlítások a második után. Egy lehetséges konfiguráció: 2, 10, 11, 12, 13, 16, 24.

Érettségi 2024 július, I.2

Annak ellenőrzésére, hogy az x=16 érték eleme-e egy tömbnek, a bináris keresést alkalmazzuk. Ennek során az x rendre a 14, 24 és 16 elemekkel van összehasonlítva. Az alábbiak közül melyek lehetnek a tömb elemei?

  1. (2, 14, 7, 24, 12, 16, 48)
  2. (14, 24, 16, 14, 24, 16)
  3. (4, 8, 9, 14, 16, 24, 48)
  4. (14, 14, 24, 24, 16, 16)

Megoldás:

Bináris keresést csak rendezett tömbben leget alkalmazni, ezért az a, b és d válaszokat kizárhatjuk. A c válasz esetén először a középső elemmel (14) történik összehasonlítás, majd, mivel a 16 ennél nagyobb, a jobb oldalon folytatjuk a keresést. Itt először a 24, majd a 16 elemekkel lesz összehasonlítva az x.

Érettségi 2024 speciális szesszió, II.2

Annak ellenőrzésére, hogy a (48, 24, 16, 14, 9, 8, 4) tömbben megvan-e az x érték, a bináris keresés algoritmusát használjuk. Tudva, hogy az x a tömb három elemével volt összehasonlítva a keresés során, adjuk meg két lehetséges értékét.

Megoldás:

Olyan értéket kell választani, amit az első és második összehasonlításban még nem találunk meg. Lehet az x például 4, 9, 16 vagy 48, de akár olyan érték is, ami nincs meg a tömbben (pl. 49, 30, 5 stb.).