Двійковий пошук

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

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

12.2.1. Дерева порівнянь на векторній пам‘яті.

Розглянемо спочатку, як можна записати дерево у векторну пам‘ять.

Нехай ключі зберігаються увекторі КЛЮЧ(i;j). Елементи у векторній пам‘яті повинні бути впорядкованими за значенням ключів.

При пошуку певного елемента зробимо коренем дерева вмістиме КЛЮЧ(т), де m = [(і+j)/2]- найбільше ціле, менше або рівне (i+j)/2. Тоді ліве піддерево розміщується у векторі КЛЮЧ(i;m-1), а праве - у векторі KЛЮЧ(m+1;j). Цей процес повторюється, доки не буде знайдений потрібний елемент, тобто доки процес не зійдеться у одній вершині, для якої обидва індекси у векторі КЛЮЧ будуть мати однакові значення.

Тоді алгоритм D пошуку ключа К у векторі КЛЮЧ(і;j) можна записати наступною послідовністю кроків:

Алгоритм D

D0. Ініціалізація індексів і, j.

D1. Повторювати кроки D2 - D5 доти, доки i<j.

D2. Обчислення індекcа кореня дерева: m=[(i+j)/2].

D3. Якщо [КЛЮЧ (m)]= К, то REZ= т, кінець.

D4. Інакше: якщо [ КЛЮЧ (т)] <K,

тo і=т +1 (пошук справа); перехід на D2.

D5. Інакше j=m-1 ( пошукзліва); перехід на D2;

Основна задача полягає у виключенні на кожному кроці з подальшого пошуку як можна більшої кількості елементів. Оптимальним рішенням буде вибір середнього елемента, оскільки при цьому буде виключена половина кількості елементів. Максимальне число порівнянь дорівнює О (log₂ n), де n- кількість елементів даних.