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

Двійковий пошук - розбір алгоритму мовою 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 і С++. Цей алгоритм можна використовувати тільки з певними структурами даних. Наприклад, сюди не підійдуть структури, які використовують зв 'язкові списки.