Алгоритми двійкового пошуку, пояснені за допомогою C ++

Бінарний пошук - це один із тих алгоритмів, з яким ви стикаєтесь на кожному (хорошому) вступному уроці інформатики. Це ефективний алгоритм пошуку елемента в упорядкованому списку. Для цього прикладу ми просто припустимо, що це масив.

Цілями двійкового пошуку є:

  • мати можливість відкидати половину масиву на кожній ітерації
  • мінімізувати кількість елементів, які ми повинні пройти
  • залиште нам одне остаточне значення

Візьмемо для прикладу такий масив цілих чисел:

int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Скажімо, ми намагаємось знайти значення індексу числа 7 у цьому масиві. Всього 17 елементів, а значення індексу переходять від 0 до 16.

Ми бачимо, що значення індексу 7 дорівнює 4, оскільки це п’ятий елемент масиву.

Але що було б найкращим способом для комп’ютера знайти значення індексу числа, яке ми шукаємо?

По-перше, ми зберігаємо значення minі max, такі як 0і 16.

int min = 0;int max = 16;

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

Зі значенням індексу від 0 до 16 у цьому масиві, середнє значення індексу цього масиву буде 8. Це містить число 14.

// This will round down if the quotient is not an integer

int guess = (min + max) / 2;

Наша здогадка тепер дорівнює 8, що в масиві 14, оскільки array[8]дорівнює 14.

Якби число, яке ми шукали, було 14, ми б закінчили!

Оскільки це не так, тепер ми відкинемо половину масиву. Це всі числа після 14, або значення індексу 8, оскільки ми знаємо, що 14 більше 7, і наша здогадка занадто висока.

Після першої ітерації наш пошук зараз знаходиться в межах: 1, 3, 4, 6, 7, 8, 10, 13

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

Оскільки наше початкове припущення 14 було більше 7, тепер ми зменшуємо його на 1 і зберігаємо в max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Тепер пошук виглядає так:

 1, 3, 4, 6, 7, 8, 10, 13
min = 0max = 7guess = 3 

Оскільки наше припущення було занадто низьким, ми відкидаємо нижню половину масиву, збільшуючи значення min, навпаки до того, що ми робили раніше max:

min = guess + 1; // min is now 4

До наступної ітерації нам залишається:

 7, 8, 10, 13min = 4max = 7guess = 5

Оскільки значення індексу 5 повертає 8, ми тепер перевищуємо ціль. Ми повторюємо процес ще раз, і нам залишається:

 7min = 4max = 4guess = 4

І нам залишається лише одне значення, 4, як індекс цільового числа, яке ми шукали, яке було 7.

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

Псевдокод для цього алгоритму виглядатиме приблизно так:

  1. Нехай min = 0і нехай max = nде nнайвище можливе значення індексу
  2. Знайдіть середнє значення minта max, округніть вниз, щоб це було ціле число. Це нашguess
  3. Якщо ми вгадали номер, зупиніться, ми його отримали!
  4. Якщо guessзанадто низький, встановіть minрівним одиниці більше ніжguess
  5. Якщо guessзанадто висока, встановіть maxрівну одиниці менше ніжguess
  6. Поверніться до другого кроку.

Ось рішення, написане на C ++: