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