Двоично търсене — Итеративен начин за търсене

Днес ще обсъдим какво е двоично търсене, как да го приложим итеративно и ползите от използването на двоично търсене за търсене на елемент в даден набор от данни.

Двоичното търсене е алгоритъм за търсене, при който разделяме даден набор от елементи от средата и сравняваме елемента, който трябва да се търси, с елемента в средата. Ако елементът е по-малък от средата, повтаряме процеса в първата половина на набора от данни, в противен случай във втората половина, докато елементът, който ще се търси, стане равен на средния елемент.

Алгоритъм

Нека разгледаме алгоритъма и да разберем как да приложим двоичното търсене.

int low = 0;
int high = arr.length - 1;

while (low <= high) {
    int mid = low + (high - low) / 2;

    if (key == arr[mid]) {
        return mid;
    } else if (key > arr[mid]) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}

return -1;

В горния кодов фрагмент вземаме два индекса, low, зададен в началото на масива, и high, зададен в последния елемент в масива.
Работен цикъл върху масива, докато low стане по-малък или равен на индекса high, ние изчисляваме индекса mid във всяка итерация.
Имайки предвид елементът, в който ще се търси, се обозначава с променлива ключ,
Ако ключ е равен на елемента в средния индекс на масива, връщаме среден.
Ако ключът е по-голям от елемента в средния индекс на масива, задаваме ниския индекс на среден+1 елемент.
Ако ключът е по-малък от елемента в средния индекс на масива, задаваме висок индекс на среден 1 елемент.
Ако ключът не е намерен в масива, връщаме -1;

Времева и пространствена сложност

Двоичното търсене следва техниката "разделяй и владей".

Времева сложност: O(logn)
Всеки път, когато попаднем на алгоритъм, който следва техника "разделяй и владей", т.е. разделя масива наполовина с всяка итерация, времевата сложност ще бъде логаритмичен.

Пространствена сложност:O(1)
Двоичното търсене, когато се изпълнява итеративно, не използва допълнително пространство и следователно консумира постоянно място по време на изпълнението си.

Използване и ползи

Той стеснява набора от данни за търсене.
Може да се използва за ефективно търсене на елемент/обект в огромен набор от данни.
Може да се използва в други алгоритми за опростяване на крайната цел на алгоритъма.

Стигнахте до края на статията и сте готови да внедрите или използвате двоично търсене в реални решения.

Ще се видим в следващата статия, а дотогава hasta luego.