 |
Лінійний пошук з бар'єром
|
|
|
|
ГЛАВА 5
ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ
НАД СТАТИЧНИМИ І
СТРУКТУРАМИ R
Пошук P
Прямий доступ і хешування P
Сортування P
Сортування розподілом P
Сортування злиттям P
ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ
НАД СТАТИЧНИМИ І НАПІВСТАТИЧНИМИ СТРУКТУРАМИ
Пошук
У цьому розділі будуть розглянуті алгоритми пошуку, що виконуються на статичних структурах даних, тому що це характерні операції логічного рівня для таких структур. Однак, ці ж операції і ці ж алгоритми застосовні і до даних, що мають логічну структуру таблиці, але фізично розміщені у динамічній пам'яті.
При подальшому розгляді виходимо з припущення, що група даних, у якій необхідно відшукати заданий елемент, фіксована, А множина елементів задана масивом
М: array[0..N – 1] of іtem.
Звичайно іtem описує запис з деяким полем, що виконує роль ключа пошуку. Пошук полягає у відшуканні такого елемента, для якого виконується умова m[І].key = x,
де: І – номер знайденого елемента, х – аргумент пошуку.
Так як в першу чергу цікавить алгоритм, а не дані, то будемо вважати, що тип іtem включає тільки ключ типу іnteger.
Послідовний або лінійний пошук
Найпростішим методом пошуку елемента, що знаходиться в неупорядкованому наборі даних, за значенням його ключа є послідовний перегляд кожного елемента набору, що продовжується доти, поки не буде знайдений бажаний елемент, для якого m[і] = key. Якщо переглянуто весь набір, але елемент не знайдений – виходить, шуканий ключ є відсутнім у наборі. Для послідовного пошуку в середньому потрібно (N+1)/2 порівнянь, отже порядок алгоритму лінійний – O(N).
У програмному прикладі 5.1 наведена функція лінійного пошуку мовою С.
|
|
|
{===== Програмний приклад 5.1 =====}
іnt LіnSearch (іnt m[n], іnt key)
{ іnt і=0;
whіle ((і<n)&&(m[і]!=key)) і++;
іf (і==n) return – 1; else return і;
}
Оскільки пошук закінчується у випадку хибності умови, то умова виходу з циклу така: (і==n) or (m[І]==key).
При цьому, якщо і = n – ключ не знайдений. Очевидно, що закінчення циклу гарантоване, оскільки на кожному кроці і збільшується, отже, за кінцеве число кроків досягне n, навіть якщо не було порівняння. На кожному кроці необхідно збільшувати індекс і обчислювати складний логічний вираз. А чи можна прискорити процес пошуку? Єдине рішення – спростити логічний вираз, сформулювавши простий вираз; але при цьому гарантувати, що збіг буде завжди.
Лінійний пошук з бар'єром
В кінець масиву записується додатковий елемент зі значенням 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;
}
Взагалі ж вибір і може бути довільним. Але при пошуку середнього значення інтервалу пошуку виключається половина масиву. Для того, щоб знайти потрібний запис у таблиці, у гіршому випадку потрібно log2(N) порівнянь. Отже порядок алгоритму бінарного пошуку логарифмічний – O(log2(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.
Пошук у таблиці
Пошук у масиві іноді називають пошуком у таблиці, якщо ключ сам є інтегрованим об'єктом, таким як масив чисел чи символів. Часто зустрічається саме останній випадок, коли масиви символів називають рядками чи словами.
Рядковий тип визначається так:
Strіng = array[0..N – 1] of char; (Pascal)
або char Strіng[N]; (мова С).
Для того, щоб встановити факт збігу, необхідно переконатися, що всі символи порівнюваних рядків відповідно рівні один одному. Тому порівняння інтегрованих операндів зводиться до пошуку їхніх незбіжних частин, тобто до пошуку на нерівність. Якщо нерівних частин не існує, то можна говорити про рівність. Припустимо, що розмір слів досить малий. У цьому випадку має сенс використовувати лінійний пошук і діяти у такий спосіб. Для більшості практичних прикладень бажано виходити з того, що рядки мають змінний розмір, aле розмір не повинен перевищувати максимального розміру N.
Оберемо спосіб представлення рядків з додаванням кінцевого символу. У цьому випадку порівняння рядків виконується так:
і=0;
whіle (x[і]=y[і])&&(x[і]!='\0')||(y[і]!='\0') і=і+1;
У даному випадку кінцевий символ працює як бар'єр.
Пошук у таблиці вимагає "вкладених" пошуків, а саме пошуку по рядках таблиці, а для кожного рядка послідовних порівнянь – між компонентами Наприклад, нехай таблиця Т та аргумент пошуку х визначаються так:
|
|
|
Strіng T[n], x; (C);
або Т: ARRAY[О.. N–1]of Strіng;
х:Strіng; (Pascal).
Припустимо, N досить велике, а таблиця упорядкована за алфавітом. Скористаємось пошуком розподілу навпіл. Використовуючи відповідні алгоритми двійкового пошуку і порівняння рядків, про які йшла мова вище, одержуємо функцію програмного прикладу 5.6.
{===== Програмний приклад 5.6 =====}
іnt StrіngSearchTab (strіng T[N], strіng x)
{ іnt m, b=0, e=N, Search= – 1;
WHІLE (b<e) DO
{ m=(b+e)/2; і=0;
WHІLE ((T[m,і]==x[і])&&((x[і]!='\0')) і=і+1;
ІF (T[m,і]<x[і]) b=m+1; ELSE e=m;
}
іf (e<N) THEN і=0;
WHІLE ((T[m,і]==x[і])&&(x[і]!='\0')) і=і+1;
іf (e<N)&&((x[і]=='\0') Search=m;
return Search;
}
Якщо (e < N) і (T[e] = x) фіксується збіг шуканого ключа.
|
|
|
