A feladat

  • Adott egy növekvő módon rendezett gyűjtemény. Az egyszerűség kedvéért legyen ez egész számok tömbje, azaz C++-ban például egy std::vector<int>. Nevezzük a tömböt array-nek.
  • Adott egy érték (value).
  • Alsó határ keresés esetén azt a legkisebb indexet (i) akarjuk meghatározni, amelyre igaz, hogy array[i] >= value.
  • Felső határ keresés esetén pedig azt a legkisebb indexet (i) keressük, amelyre igaz, hogy array[i] > value.

Ha a keresett érték benne van a növekvő módon rendezett tömbben – esetleg akár többször is – akkor annak legkisebb indexű, azaz első előfordulási helyét adja meg az alsó határ keresés. A felső határ keresés pedig az első olyan elem helyét adja vissza, ami már nagyobb a keresett értéknél. Ebből az is könnyen látható, hogy a két eredmény különbsége megadja, hogy a keresett elem hányszor fordul elő a tömbben.

Ha a keresett érték nincs benne a tömbben, akkor mindkét algoritmus eredménye az első olyan elem indexe lesz, amely nagyobb a keresett értéknél. Ha a keresett érték nagyobb a tömb utolsó eleménél, akkor mindkét algoritmus a tömb méretével egyező indexet szolgáltat, azaz “túlindexelnek” a tömbön.

A megoldás

Mivel rendezett tömbökről van szó, ezért induljunk ki a rendezett tömböknél jól ismert bináris keresés algoritmusából.

Bináris keresés

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

size_t BinarySearch(const std::vector<int>& array, const int value)
{
    int leftIndex = 0;
    int rightIndex = array.size() - 1;
    auto middleIndex = (leftIndex + rightIndex) / 2;

    while (leftIndex <= rightIndex && array[middleIndex] != value) {
        if (value < array[middleIndex]) {
            rightIndex = middleIndex - 1;
        } 
        else { 
            leftIndex = middleIndex + 1;
        }
        middleIndex = (leftIndex + rightIndex) / 2;
    }

    return (leftIndex > rightIndex) ? array.size() : static_cast<size_t>(middleIndex);
}

Magát a bináris keresés működését itt nem szeretném elmagyarázni, viszont néhány részletre felhívnám a figyelmet.

  • A 4. sorban rightIndex típusa azért nem size_t, mert ha 0 elemű lenne a bemeneti tömb, akkor alulcsordulna a változó. Mivel leftIndex és rightIndex típusát azonosnak érdemes választani, ezért lett a leftIndex is size_t típusú. Mivel middleIndex-et a két másik indexből számítjuk ki, ezért annak a típusa is int lesz. Emiatt viszont a 17. sorban kasztolunk a kimeneti típusra, bár ezt implicit módon is megtenné a függvény.
  • A 7. sorban kezdődő ciklus addig fut, amíg leftIndex nem nagyobb rightIndex-nél, illetve amíg nem találjuk meg a keresett elemet. Érdemes azt átgondolni, hogy a leftIndex <= rightIndex feltétel akkor lesz hamis, ha a keresett érték nincs benne a tömbben.

Alsó határ keresés

A bináris keresésre építve már meg tudjuk alkotni az alsó határ keresés algoritmusát, csak azt kell átgondolnunk, hogy miben különbözik a megoldandó feladat.

  • Ha megtaláljuk a keresett értéket valahol a tömbben, akkor még nem állhat le a keresésünk, mivel lehetséges, hogy a találati hely előtt is előfordul még a keresett érték. Ezért két dolgot kell tennünk:
    • A ciklus feltételből ki kell szednünk az array[middleIndex] != value feltételt.
    • Találat esetén is folytatnunk kell a keresést a találati hely előtti részen.
  • Ha az algoritmus során találunk egy olyan tömbbeli elemet, mely nagyobb egyenlő a keresett értéknél (value <= array[middleIndex]), akkor ennek az elemnek az indexét el kell tárolnunk egy változóban. Ezután folytatjuk a keresést a találati helytől balra lévő tömbrészen.
  • A keresést addig folytatjuk, amíg “el nem fogy a tömb”, azaz amíg a vizsgált tömbrész elejét és végét jelző indexek hibás pozícióba nem kerülnek (leftIndex > rightIndex).
  • Ha olyan elemet keresünk a tömbben, ami minden tömbbeli elemnél nagyobb, akkor a value <= array[middleIndex] feltétel soha nem fog teljesülni a cikluson belül. Ilyenkor az algoritmus eredményének túl kell indexelnie a tömbön, ezért a result kezdeti értékét a tömb méretének választjuk.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

size_t LowerBound(const std::vector<int>& array, const int value)
{
    int leftIndex = 0;
    int rightIndex = array.size() - 1;
    auto middleIndex = (leftIndex + rightIndex) / 2;
    size_t result = array.size();

    while (leftIndex <= rightIndex) {
        if (value <= array[middleIndex]) {
            rightIndex = middleIndex - 1;
            result = static_cast<size_t>(middleIndex);
        }
        else {
            leftIndex = middleIndex + 1;
        }
        middleIndex = (leftIndex + rightIndex) / 2;
    }

    return result;
}

Felső határ keresés

A felső határ keresés algoritmusa már nagyon egyszerűen megadható az alsó határ keresés ismeretében. Csak annyit kell módosítanunk, hogy a keresés során vizsgált feltételben nem engedjük meg az egyenlőséget, tehát value < array[middleIndex]-et fogunk vizsgálni.

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

size_t UpperBound(const std::vector<int>& array, const int value)
{
    int leftIndex = 0;
    int rightIndex = array.size() - 1;
    auto middleIndex = (leftIndex + rightIndex) / 2;
    size_t result = array.size();

    while (leftIndex <= rightIndex) {
        if (value < array[middleIndex]) {
            rightIndex = middleIndex - 1;
            result = static_cast<size_t>(middleIndex);
        }
        else {
            leftIndex = middleIndex + 1;
        }
        middleIndex = (leftIndex + rightIndex) / 2;
    }

    return result;
}

Kapcsolódó kódok

A kódok github-on is elérhetők.