Двійковий пошук-розбір алгоритму на мові c++

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

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

Послідовний (лінійний) пошук

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

• Порівнюємо значення ключа зі значенням елемента масив.
• Якщо значення рівні, повертаємо отримане значення.
• Якщо немає-збільшуємо значення змінної циклу на одиницю і порівнюємо з наступним елементом масиву.

Індексно-послідовний пошук

Більш ефективний спосіб пошуку значення у відсортованому масиві. Але більш вимогливий до ресурсів.

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

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

• Спочатку дізнаємося значення об`єкта в середині масиву. Перевіряємо на відповідність з вихідним значенням.
• Якщо значення з середини менше вихідного, то продовжуємо пошук у другій половині, якщо більше-шукаємо в першій.
• В вийшла половині чинимо таким же чином: ділимо її на половину і порівнюємо вийшло значення.

Пошук відбувається до моменту, поки початкове значення не стане дорівнює значенню в масиві. Якщо такого не відбувається-значить даного значення в масиві немає.

Є кілька підводних каменів, які можуть зустрітися при проектуванні двійкового пошуку.

Переповнення вибраного типу даних

Щоб дізнатися значення в середині масиву, необхідно скласти праве і ліве значення, і розділити на два. Тобто:

Середина масиву = ліве значення + (ліве значення-праве значення) / 2

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

Помилки значень

Або помилки на одиницю. Дуже важливо врахувати наступні варіанти:

• Порожній масив.
• Значення відсутнє.
• Вихід за межі масиву.

Кілька екземплярів

Необхідно врахувати, що в разі існування в масиві декількох однакових екземплярів ключа програма повинна знаходити певний (перший, останній, наступний за ним).

Розберемо реалізації даного алгоритму в мові програмування C плюс плюс. Необхідно враховувати, що двійковий пошук працює тільки з відсортованим масивом! Якщо масив попередньо не відсортувати, то результат обчислень буде невірним.

Нижче наведено код на C ++. Спочатку ініціалізується масив цілочисельних змінних arr, розміром десять. Далі оператор cin в циклі for очікує введення десяти значень від користувача (рядок десять).

У двадцятому рядку програма чекає від користувача введення значення ключа.

Рядки 29-35 являють собою реалізований алгоритм бінарного пошуку. В ході виконання програми в змінну mid записується значення середнього елемента за формулою:

Середина масиву (mid) = (ліве значення ( l) + праве значення (r)) / 2

Рядок

arr[mid]==key

Перевіряється, чи середнє значення дорівнює значенню ключа. Якщо дорівнює, то значення змінної flag змінюється на значення істина, тобто задача вирішена.

Якщо ж серединне значення більше значення нашого ключа, то правій частині (змінна r) присвоюється mid. Якщо навпаки, то mid кладеться в r.

Останнє-це перевірка булевої змінної flag.

Переваги бінарного пошуку

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

Недостатки

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