Алгоритми злиття

Else

Else

While A[i] К do

і < і + 1

if і < п

return і

return –1

Якщо вхідний список впорядкований, то можна скористатися ще одним вдосконаленням: пошук в такому списку можна завершувати, як тільки зустрінеться елемент, не менший ключа пошуку.

Алгоритм в найгіршому та найсприятливішому випадках є лінійним.

Бінарний пошук порівнює ключ К з середнім елементом масиву А[ т ]. Якщо вони рівні, то алгоритм закінчує роботу. В противному випадку та же операція рекурсивно повторюється для першої половини масиву, якщо К<А[ т ], і для другої, якщо К>А[ т ]:

Приклад: Знайти ключ К=70, застосував алгоритм бінарного пошуку до масиву

Ітерації алгоритму показані у наступній таблиці:

Бінарний пошук засновано на рекурсії, але його легко реалізувати як не рекурсивний алгоритм. Розглянемо псевдокод:

Алгоритм BinarySearch (А [0.. п- 1], К)

// Вхідні данні: Масив А[0.. п -1], впорядкований у зростаючому порядку

//та ключ К

//Вихідні данні: Індекс елементу масиву, рівного К,

// або —1, якщо такого елементу немає

l 0; r п —1;

while l r do

m

if К=А[ т ]

return m

else if К<А[ т ]

r m -1

l m +l

return — 1

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

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

Алгоритм Merge (В[0..р-1]. С[0..q-1], А[0..р+q-1])

// Злиття двох впорядкованих масивів в один

// Вхідні данні: Впорядковані масиви В[0..р—1] та C[0..q-i]

// Вихідні данні: Впорядкований масив А[0..р+q—1],

// що складається з елементів В к С

i0; j0; к0

while i <р and j<q do

if В[ i ] C[ j ]

A[ k ] B[ i ]; ii +l

Дата добавления: 2014-01-07