Вступ
Ми натрапили на групу математиків, які водночас є авторами-виконавцями.
Вони написали пісню про кожне зі своїх улюблених чисел, а улюблених чисел у них, як можна уявити, багато (наприклад, 0 чи 73, або 6174).
Нам цікаво почути пісню про своє улюблене число, але через таку кількість пісень, які треба перебрати, пошук потрібної може зайняти чимало часу.
На щастя, вони впорядкували свої пісні в плейлист, відсортований за назвою, а назва - це просто число, якому присвячено пісню.
Ми розуміємо, що можемо скористатися алгоритмом двійкового пошуку, щоб швидко знайти пісню за назвою.
Вказівки
Наше завдання - реалізувати алгоритм двійкового пошуку.
Алгоритм двійкового пошуку знаходить елемент у масиві, раз за разом ділячи його навпіл і зберігаючи лише ту половину, яка містить шуканий елемент.
Це дає змогу швидко звужувати коло можливих місць розташування шуканого елемента, доки ми його не знайдемо або доки не виключимо всі можливі місця.
Двійковий пошук працює лише тоді, коли масив відсортовано.
Алгоритм має такий вигляд:
- Знайти середній елемент відсортованого масиву і порівняти його з шуканим елементом.
- Якщо середній елемент збігається з шуканим, ми закінчили!
- Якщо середній елемент більший за шуканий, ми можемо виключити цей елемент і всі елементи після нього.
- Якщо середній елемент менший за шуканий, ми можемо виключити цей елемент і всі елементи перед ним.
- Якщо виключено всі елементи масиву, то шуканого елемента в масиві немає.
- Інакше повторімо процес на тій частині масиву, яку ще не виключено.
Ось приклад:
Припустімо, ми шукаємо число 23 у такому відсортованому масиві: [4, 8, 12, 16, 23, 28, 32].
- Спочатку ми порівнюємо 23 із середнім елементом, 16.
- Оскільки 23 більше за 16, ми можемо виключити ліву половину масиву, і в нас залишиться
[23, 28, 32].
- Далі ми порівнюємо 23 з новим середнім елементом, 28.
- Оскільки 23 менше за 28, ми можемо виключити праву половину масиву:
[23].
- Ми знайшли шуканий елемент!
