Bináris keresés

Szekvenciális keresés: egyesével végignézzük az elemeket.

Ha egy tömb rendezett, tudunk benne hatékonyabban keresni: minden körben a középső (vagy egyik középső) elemet nézzük meg és a tömbnek csak abban a “felében” folytatjuk a keresést (ugyanígy tovább), ahol esélyünk van megtalálni a számot. Ezt az eljárást nevezzük bináris keresésnek.

Példa (az n elemű t tömbben keressük x-et):

    n = 8
    t: 1 3 4 8 9 20 30 50
      [      *           ]
      [     ]
         *
          [ ]

    x = 7

Feladat:

Adott egy tömb növekvő sorrendbe rendezett egész számokból. Adott még egy x érték. Írjuk ki, hogy megvan-e x a tömbben (igen/nem)!

Megoldás szekvenciális kereséssel

 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

#include <iostream>
using namespace std;

int main()
{
    cout << "n = ";
    int n;
    cin >> n;

    cout << "a tomb elemei: ";
    int t[1000];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    int x;
    cout << "x = ";
    cin >> x;


    bool megvan = false;

    for (int i = 0; i < n; i++) {
        if (t[i] == x)
            megvan = true;
    }

    if (megvan)
        cout << "igen" << endl;
    else
        cout << "nem" << endl;

    return 0;
}

Megoldás bináris kereséssel

 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
46
47

#include <iostream>
using namespace std;

int main()
{
    cout << "n = ";
    int n;
    cin >> n;

    cout << "a tomb elemei: ";
    int t[1000];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    int x;
    cout << "x = ";
    cin >> x;


    bool megvan = false;

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

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

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

    if (megvan)
        cout << "igen, a(z) " << bal << " indexen" << endl;
    else
        cout << "nem" << endl;

    return 0;
}

HF.

Kövessük nyomon az algoritmus futását a

    10
    1 3 4 5 6 8 8 10 20 56

tömbre és a 10, 11, 1, 56, 0, 57 keresett értékekre külön-külön!

Változatok

1.

Adott egy csökkenő sorozat és egy keresett érték, döntsük el bináris kereséssel, hogy megvan-e a sorozatban, ha igen, írjuk ki valamelyik előfordulásának (0-alapú) indexét.

HF

2.

Keressük meg egy növekvő sorozatban az x szám első előfordulásának a helyét (ha nincs meg, akkor a válasz -1).

Pl. bemenet:
    6
    1 3 3 3 3 4
    3
kimenet:
    1
    (a 3-as első előfordulása az 1-es indexen van)

 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

#include <iostream>
using namespace std;

int main()
{
    cout << "n = ";
    int n;
    cin >> n;

    cout << "a tomb elemei: ";
    int t[1000];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    int x;
    cout << "x = ";
    cin >> x;

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

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

        if (t[kozep] >= x) {
            jobb = kozep;
        }
        else if (t[kozep] < x) {
            bal = kozep + 1;
        }
    }

    // itt biztos, hogy bal==jobb
    // ha t[bal] == x, akkor ez az első
    if (t[bal] == x)
        cout << "az elso elofordulas helye: "
             << bal << endl;
    else
        cout << "nincs x";

    return 0;
}

3.

Keressük meg egy növekvő sorozatban az x szám utolsó előfordulásának a helyét (ha nincs meg, akkor a válasz legyen az első nála nagyobb elem helye, illetve ha ilyen sincs, akkor a válasz -1).

Pl. bemenet:
    6
    1 3 3 3 3 4
    3
kimenet:
    4
    (a 3-as utolsó előfordulása a 4-es indexen van)

 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
46
47
48
49
50
51

#include <iostream>
using namespace std;

int main()
{
    cout << "n = ";
    int n;
    cin >> n;

    cout << "a tomb elemei: ";
    int t[1000];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    int x;
    cout << "x = ";
    cin >> x;

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

    while (bal < jobb) {
        int kozep = (bal + jobb + 1) / 2;

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

    // bal == jobb (biztos)

    if (t[bal] == x) {
        cout << "az utolso elofordulas indexe: "
             << bal;
    }
    else if (t[bal] < x && bal == n-1) {
        cout << "nincs elem, ami >= x (-1)" << endl;

    }
    else if (t[bal] < x) {
        cout << "az elso x-nel nagyobb elem indexe: "
             << bal+1;
    }
    else { // t[bal] > x
        cout << "az elso x-nel nagyobb elem indexe: "
             << bal;
    }

    return 0;
}

4.

Határozzuk meg egy n természetes szám négyzetgyökének az egészrészét (sqrt nélkül).

Megoldás bináris kereséssel:

 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

#include <iostream>
using namespace std;

int main()
{
    cout << "n = ";
    int n;
    cin >> n;

    int a = 0, b = n;

    int eredmeny = -1;

    while (a < b && eredmeny == -1) {
        int k = (a+b+1) / 2;

        if (k*k < n) {
            a = k;
        }
        else if (k*k == n) {
            eredmeny = k;
        }
        else { // >
            b = k-1;
        }
    }
    // itt a == b mindig ha az eredmeny nincs
    // beallitva

    if (eredmeny == -1) {
        cout << a << endl;
    }
    else
        cout << eredmeny << endl;

    return 0;
}

Vagy eredmény változó nélkül:

 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

#include <iostream>
using namespace std;

int main()
{
    cout << "n = ";
    int n;
    cin >> n;

    int a = 0, b = n;

    while (a < b) {
        int k = (a+b+1) / 2;

        if (k*k <= n) {
            a = k;
        }
        else { // >
            b = k-1;
        }
    }

    // itt a == b mindig
    cout << a << endl;

    return 0;
}

Megoldás szekvenciális kereséssel (lassabb):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
using namespace std;

int main()
{
    cout << "n = ";
    int n;
    cin >> n;

    int eredmeny = 0;

    while (eredmeny*eredmeny <= n)
        eredmeny++;

    eredmeny--;

    cout << eredmeny << endl;
    return 0;
}