Послідовний або лінійний пошук

Настройка печати производится опцией Print Setup в меню File.

9.2. Вывод на печать

	Вывод на печать осуществляется с помощью опции Print в меню File. «Горячая» клавиша режима Print выглядит следующим образом.

ГЛАВА 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, навіть якщо не було порівняння. На кожному кроці необхідно збільшувати індекс і обчислювати складний логічний вираз. А чи можна прискорити процес пошуку? Єдине рішення – спростити логічний вираз, сформулювавши простий вираз; але при цьому гарантувати, що збіг буде завжди.