Алгоритм бінарного пошуку числа в масиві

Метод бінарного пошуку індексів даного елемента-ключа в відсортованих масивах 

Теоретичний компонент 

Нехай впорядкований масив х з п елементів містить значення

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179 

і нехай заданий аргумент пошуку число-ключ, що рівний, наприклад, 129

Ідея алгоритму бінарного пошуку така:

• порівняти аргумент пошуку ключа зі значенням середнього елемента х [індекса] масиву х,

де індекс = [с/2], а [з] ціла частина числа с

• якщо вони рівні, то пошук завершено, інакше, якщо ключ < х [середовищ], виконати аналогічним чином пошук в позиціях масиву х,попередніх позиції середовищ, в іншому випадку, якщо ключ> х [середовищ], виконати аналогічним чином пошук в позиціях масиву х, Наступних за позицією середовищ

Виключити з подальшого розгляду частину масиву дозволяє той факт, що масив впорядкований

Проілюструємо процес бінарного пошуку. Число елементів масиву п = 17, тоді[17/ 2] = 8 Тому спочатку виконується порівняння з з індексів більших ніж 8, крайній елемент = 57.  Так як > 8, то зона пошуку на наступному кроці обмежується ділянкою від 9-го елемента до 17-го Ця ділянка складається з девяти елементів і його серединою є елемент х13= 107 ([(9 + 17) / 2] = 13) Оскільки середовищ> x13, то зона пошуку обмежується ділянкою від 14-го до 17-го елементу Його серединою є елементx15   На цьому процес пошуку завершений, так якх15 = середовищВідобразимо на рис 93 процес пошуку елемента ключ = 129, виділяючи у вигляді підкреслення на кожному кроці зони пошуку

Ітерація 0	5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179
Ітерація 0	5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179
Ітерація 1	5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179
Ітерація 3	5 7 11 18 26 32 44 57 81 90 94 97 107 116 129147 179 Рис 93 Приклад дихотомії

Кожне порівняння зменшує число можливих кандидатів у 2 рази Максимальне число кроків пошуку буде в тому випадку, коли аргумент пошуку знаходиться на початку або в кінці масиву У цьому випадку буде потрібно log2n + 1 ітерацій Дійсно, якщо число елементів у масиві дорівнює п = 2т, ключ буде знайдений, коли нерозглянутим залишиться тільки один елемент, тобто через т кроків У свою чергу, при заданому п маємо т = log2n Після аналізу останнього елемента отримуємо загальне число ітерацій log2n + 1 Тому обчислювальна складність бінарного пошуку складає O (log2n)

Однак наведений алгоритм не дозволяє в загальному випадку точно вирішити завдання пошуку, коли файл або масив містять повторювані значення ключів Розглянемо, наприклад, масив

5  7  11  18  26  32  44  57  81  90  94  97  107  129  129  147  179

в якому елемент (Ключ)129 міститься 2 рази Тоді, якщо аргумент пошуку буде дорівнює 129, алгоритм, як і колись, вкаже, що ключ знаходиться в 15-й позиції, тобто буде знайдено не перше, а друге значення ключа 129 (перше значення ключа розташоване в позиції 14) У ряді випадків ця помилка принципова, тоді вона усувається в результаті очевидною модифікації алгоритму бінарного пошуку

Практичний  компонент

Алгоритм бінарного пошуку  числа

 в  відсортованому масиві  на мові Python

#Функція пошуку найближчої лівої межі (від індексу шуканого числа) у відсортованому масиві   чисел

def left_bound(A,key):

 left=-1

 right=len(A)

 while right-left>1:

     middle=(right+left)//2

     if A[middle]<key:

         left=middle

     else:

        right=middle

 return left

#Функція пошуку найближчої правої межі (від індексу шуканого числа) у відсортованому масиві   чисел

def right_bound(A, key):

 left=-1

 right=len(A)

 while right-left>1:

     middle=(right+left)//2

     if A[middle]<=key:

         left=middle

     else:

        right=middle

 return  right

#Основний алгоритм з використання модуля випадкових чисел

import random      # оголошується виклик для використання модуля випадкових чисел

n=10                           # оголошується  кількість елементів(чисел) в масиві

A=[0]*n                       # оголошується  нульові елементи(усі числа 0) в масиві

key=random.randint(0,9)    # генерується випадкове число-ключ, яке треба знайти під час пошуку

for j in range(0, n):             # генерується відсортований числовий масив, в якому вестиму   пошук номера індексу елемента масиву, який дорівнює числу-ключа                        

 A[j]=j     # оголошується  черговий елемент(число) в масиві (це те, що є тілом циклу з лічильником)

# A=[0,1,1,2,2,3,3,3, 8,9] # допоміжний масив для тестування правильності алгоритму

# A=[0,0,0,2,2,3,3,6, 6,6] # допоміжний масив для тестування правильності алгоритму

# A=[2,2,2,2,2,3,4,5,6, 9] # допоміжний масив для тестування правильності алгоритму

# A=[0,1,2,2,2,2,2,2, 3,4] #  допоміжний масив для тестування правильності алгоритму

# A=[5,5,5,5,5,5,5,5, 5,5] #  допоміжний масив для тестування правильності алгоритму

right=-10

print 'key=', key

left=left_bound(A,key)    #  виклик допоміжної функції для пошуку найближчої лівої межі.

right=-10

print A,'індекс лівої межі1=', left,'для числа', key

print A,'індекс правої межі1=',right,'для числа', key

right=right_bound(A,key)     #  виклик допоміжної функції для пошуку найближчої правої межі.

print A,'індекс правої межі2=',right,'для числа', key

print A,'індекс лівої межі2=', left,'для числа', key

print 'різниця між правою та лівою межами=', right-left-1

if (A[right-1]==key)or(A[left]==key):   #  виклик повного розгалуження для перевірки правильності знайденого елемента і виведення результатів пошуку на екран

     print 'Знайдено число ', key, 'в даному масиві'

     print  'Діапазон шуканих елементів: A1[',left+1,'] =', A[left+1],' до A2[',right-1,'] =',A[right-1]

     print  'Кількість рівних шуканих чисел', right-left-1

else:

    print  'Не існує даного числа в даному масиві'

    print  'A1[',left,'] =', A[left]

    print  'A2[',right-1,'] =', A[right-1]

for j in range(left, right-1):       # оголошення циклу з лічильником для виявлення усього діапазону знайдених елементів і виведення результатів пошуку на екран

    print  j+1, '-ий шуканий елемент: A[',j+1,'] =', A[j+1]

Тестувальний компонент

Довідковий компонент

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

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

Загальний алгоритм пошуку можна описати так:

1. Обчислення елемента, що часто передбачає отримання значення елемента, ключа елемента і т.д.
2. Порівняння елемента з еталоном або порівняння двох елементів.
3. Перебір елементів множини, тобто проходження по елементах масиву.

Різняться види пошуку методом перебору і стратегіями пошуку. В лінійних структурах існують такі основні алгоритми.

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

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

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

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

Бінарний або двійковий пошук

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

Перевагами такого пошуку є швидкість пошуку, якщо порівнювати з послідовним пошуком. Але є й такий недолік, що двійковий пошук може використовуватись лише на упорядкованій множині.

Інтерполяційний пошук

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

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


https://www.ua5.org/pascal/