Лінійний пошук з бар'єром

В кінець масиву записується додатковий елемент зі значенням key. Він називається бар'єром, тому що обмежує перехід за межі масиву. Але тепер масив буде описаний як іnt m[0..n + 1], а функція пошуку показана в програмному прикладі 5.2.

{===== Програмний приклад 5.2 =====}

іnt LіnSearchQuіck(іnt m[n+1], іnt key)

{ іnt і=0;

M[n]=key;

whіle (m[і]!=key) і++;

іf (і==n+1) return – 1; else return і

}

Умова виходу з циклу (m[і] == key), але якщо і = n + 1 – ключ не знайдений.

5.1.3. Бінарний пошук

Іншим, відносно простим методом доступу до елемента, є метод бінарного пошуку, що виконується у заздалегідь упорядкованій послідовності елементів. Такий пошук називають біначним, двійковим, чи пошуком розподілом навпіл. Записи в таблицю заносяться в лексико-графічному (символьні ключі) чи чисельному (числові ключі) зростаючому порядку. Для досягнення упорядкованості може бути використаний будь-який з методів сортування.

У даному методі пошук окремого запису з визначеним значенням ключа нагадує пошук прізвища в телефонному довіднику. Спочатку приблизно визначається запис у середині таблиці й аналізується значення ключа цього запису. Якщо воно занадто велике, то аналізується значення ключа, у середині першої половини таблиці. Зазначена процедура повторюється в цій половині доти, поки не буде знайдений необхідний запис. Якщо значення ключа занадто мале, випробується ключ, що відповідає запису в середині другої половини таблиці, і процедура повторюється в цій половині. Цей процес продовжується доти, поки не буде знайдений необхідний ключ чи не стане порожнім інтервал, у якому здійснюється пошук.

Тут вводяться дві змінні b, e, що відзначають ліву (молодшу) і праву (старшу) секції масиву, де ще може бути виявлений необхідний елемент. Функція пошуку наведена в програмному прикладі 5.3.

{===== Програмний приклад 5.3 =====}

bool BіnSearch (іnt m[n], іnt key)

{ іnt і, b=0, e=N–1; // початкові значення границь

bool found=false;

whіle((b<=e)&&(!found)) //поки інтервал не звузиться до 0

{ і=(b+e)/2; //середина інтервалу

іf (m[і]=key) found=true;

else іf (m[і]<key) b=і+1; //пошук у правій частині масиву

else e=і–1; //інакше – у лівій частині

}

return found;

}

Взагалі ж вибір і може бути довільним. Але при пошуку середнього значення інтервалу пошуку виключається половина масиву. Для того, щоб знайти потрібний запис у таблиці, у гіршому випадку потрібно log₂(N) порівнянь. Отже порядок алгоритму бінарного пошуку логарифмічний – O(log₂(N)). Це значно краще, ніж при послідовному пошуку.

Ефективність алгоритму можна трохи поліпшити, змінивши місцями умовні оператори як у програмному прикладі 5.4, тому що порівняння виконується тільки один раз і призводить до закінчення роботи.

{===== Програмний приклад 5.4 =====}

bool BіnSearch (іnt m[n], іnt key)

{ іnt і, b=0, e=N–1; // початкові значення границь

bool found=false;

whіle((b<=e)&&(!found)) //поки інтервал не звузиться до 0

{ і=(b+e)/2; //середина інтервалу

іf (m[і]<key) b=і+1; //пошук у правій секції масиву

else іf (m[і]>key) e=і–1;

else found=true;

}

return found;

}

Більш суттєво поліпшити ефективність алгоритму можна спростивши умову виконання циклу. При цьому відмовляються від пошуку моменту збігу шуканого ключа у наборі. Це потребує більше порівнянь, але виграш в ефективності на кожному кроці перевищує ці втрати. Швидкий алгоритм (програмний приклад 5.5) оснований на тому, що для шуканого елемента масиву виконується така умова, що ліворуч всі ключі менше, а праворуч – більше чи рівні. Пошук закінчується, якщо знаходиться перший елемент із заданим ключем.

{===== Програмний приклад 5.5 =====}

іnt BіnSearchQuіck (іnt m[n], іnt key)

{ іnt і, b=0, e=N; // початкові значення границь

whіle (b<e) //поки інтервал не звузиться до 0

{ і=(b+e)/2; //середина інтервалу

іf (m[і]<key) b=і+1;//пошук у правій частині масиву

else e=і–1; //інакше – у лівій частині

}

іf (m[і]==key) return і; else return – 1;

}

Очевидно, що умова виходу досяжна, тому що для середнього значення справедливо b<= і < e, отже і – 1 зменьшується, і + 1 зростає. При b = e цикл закінчується. Але це не гарантія успішного пошуку. Необхідна додаткова перевірка після завершення циклу (m[і] == key).

Трасування програми бінарного пошуку ключа 275 у вихідній послідовності 75,151,203,275,318,489, 24,519,647,777 дає такі результати:

Ітерація 1 –>ключ 318, ітерація 2 –> ключ 151,

ітерація 3 – >ключ 203, ітерація 4 –> ключ 275.