Алгоритм двійкового пошуку
Алгоритм (двійкового) бінарного пошуку забезпечує швидкий пошук у відсортованих масивах чи колекціях. Цей ітеративний підхід до пошуку ігнорує приблизно половину значень колекції з кожним проходом, що забезпечує масштабованість.
Коли вам потрібно знайти позицію елемента в колекції, що сортується, алгоритм двійкового пошуку забезпечує відповідний і швидкий підхід. Цей алгоритм включений до загального класу List , який був впроваджений у .NET framework версії 2.0. Хоча це означає, що зазвичай вам не потрібно відтворити його, цікаво зрозуміти, як працює цей алгоритм.
Алгоритм бінарного пошуку є ітеративним. Протягом кожної ітерації ви вибираєте центральний елемент у масиві відповідно до його індексу. Якщо знайдене значення є тим, що ви шукаєте, алгоритм завершено. Припускаючи, що масив сортується з найменшими значеннями, якщо значення в середній точці менше, ніж пошук елемента, середня точка і всі елементи перед її відкиданням, зменшуючи вдвічі розмір інших елементів. Якщо значення середньої точки більше, ніж елемент пошуку, всі елементи цього індексу в кінець масиву будуть відкинуті. Ці елементи можна ігнорувати, оскільки колекція сортується. Якщо це не так, метод бінарного пошуку не працює.
Коли розмір масиву зменшується вдвічі, процес повторюється. Кожна ітерація видаляє половину можливого значення або ідентифікує елемент, який ви хочете знайти. Це продовжується, поки елемент не буде знайдений або поки всі елементи не будуть виключені з пошуку, після чого ви дізнаєтеся, що елемент пошуку відсутній.
Насправді зазвичай неефективно фактично видаляти елементи з масиву або колекції. Набагато ймовірніше, що ви будете використовувати покажчики длявизначення першого та останнього індексу пошуку. Вони ініціалізуються, щоб вказувати на перший та останній елементи у послідовності, і один із покажчиків переміщається під час кожної ітерації, щоб зменшити вдвічі ефективнішу довжину колекції.
Розгляньмо приклад, використовуючи наведені нижче значення, шукаємо номер тридцять шість.
На першій ітерації ми розпочнемо з визначення середини. Оскільки в колекції є парна кількість елементів, ми можемо вибрати або десятий або одинадцятий елемент. Рішення довільне, тому давайте використовувати найлівіші із середніх значень, що становить сорок вісім.
Сорок вісім більше від числа, для якого ми шукаємо. Це означає, що всі предмети з вищими індексами також повинні бути більше тридцяти шести, тому ми можемо ігнорувати більшу половину колекції. Потім ми можемо знайти середню точку меншого набору значень, що становить двадцять дев'ять.
Двадцять дев'ять менше від числа, яке ми хочемо знайти, щоб ми могли ігнорувати його і всі цінності під ним. Це залишає лише чотири елементи для пошуку. Коли ми знаходимо середину цих елементів, ми виявляємо, що саме тридцять шість ми мали намір знайти. Це означає, що нам вдалося знайти двадцять елементів лише за три ітерації.
Давайте реалізуємо алгоритм бінарного пошуку з використанням C#. Ми створимо метод для виконання двійкового пошуку за відсортованим масивом цілих чисел. Вважатимемо, що масив відсортований у порядку зростання. Значення, що повертається для методу, буде індексом елемента пошуку або -1, якщо елемент не знайдений.
Для початку додайте наступну сигнатуру методу класу, який був автоматично згенерований при створенні проекту. Метод має два параметри. Першийотримує масив для пошуку, а другий номер.
Замість того, щоб намагатися зменшити розмір масиву під час кожної ітерації, ми використовуватимемо покажчики для початку і кінця «шматка» масиву, в якому знаходиться елемент, що шукається. На початку процесу це весь масив. Тому покажчик початку вказуватиме на нульовий індекс, а кінцевий покажчик буде менше довжини масиву.
Щоб налаштувати покажчики та викликати ітеративну частину алгоритму, додайте наступний код до методу SearchBinary:
Рекурсивний метод пошуку
Рекурсивна частина алгоритму має чотири частини:
- Переконайтеся, що початкові та кінцеві покажчики все ще дійсні, вказавши довжину масиву, яка більша за нуль. Якщо елемент, який ми шукаємо, не існує в масиві, після останньої ітерації початкові та кінцеві покажчики перекриватимуться, даючи шматок масиву без елементів. Якщо це станеться, ми повернемо -1, щоб зазначити, що елемент відсутній.
- Знайдіть індекс середньої точки інших предметів. Це легко обчислюється з використанням покажчика початку і довжини елемента, що залишився.
- Перевірте, чи є елемент у середній точці значенням, яке хочемо знайти. Якщо це так, ми повернемо індекс середньої точки і алгоритм закінчиться.
- Переконайтеся, що елемент у середній точці більший за пошуковий запит. Якщо це так, ми перемістимо кінцевий покажчик на один елемент до середини і почнемо наступну ітерацію з кроку 2 вище. Якщо ні, середнє значення має бути менше, ніж елемент пошуку, тому ми перемістимо покажчик початку елемент відразу після середини і повернемося до кроку 2.
Щоб випробувати алгоритм пошуку, додайте наступний код у метод main та покрокове виконання коду у налагоджувачі,щоб побачити результати, або додайте в кінціConsole.WriteLine(index);.
статті IT, сі шарп, алгоритми