Вступ
Ми натрапили на групу математиків, які водночас є авторами-виконавцями.
Вони написали пісню про кожне зі своїх улюблених чисел, а улюблених чисел у них, як можна уявити, багато (наприклад, 0 чи 73, або 6174).
Нам цікаво почути пісню про своє улюблене число, але через таку кількість пісень, які треба перебрати, пошук потрібної може зайняти чимало часу.
На щастя, вони впорядкували свої пісні в плейлист, відсортований за назвою, а назва - це просто число, якому присвячено пісню.
Ми розуміємо, що можемо скористатися алгоритмом двійкового пошуку, щоб швидко знайти пісню за назвою.
Вказівки
Наше завдання - реалізувати алгоритм двійкового пошуку.
Алгоритм двійкового пошуку знаходить елемент у масиві, раз за разом ділячи його навпіл і зберігаючи лише ту половину, яка містить шуканий елемент.
Це дає змогу швидко звужувати коло можливих місць розташування шуканого елемента, доки ми його не знайдемо або доки не виключимо всі можливі місця.
Двійковий пошук працює лише тоді, коли масив відсортовано.
Алгоритм має такий вигляд:
- Знайти середній елемент відсортованого масиву і порівняти його з шуканим елементом.
- Якщо середній елемент збігається з шуканим, ми закінчили!
- Якщо середній елемент більший за шуканий, ми можемо виключити цей елемент і всі елементи після нього.
- Якщо середній елемент менший за шуканий, ми можемо виключити цей елемент і всі елементи перед ним.
- Якщо виключено всі елементи масиву, то шуканого елемента в масиві немає.
- Інакше повторімо процес на тій частині масиву, яку ще не виключено.
Ось приклад:
Припустімо, ми шукаємо число 23 у такому відсортованому масиві: [4, 8, 12, 16, 23, 28, 32].
- Спочатку ми порівнюємо 23 із середнім елементом, 16.
- Оскільки 23 більше за 16, ми можемо виключити ліву половину масиву, і в нас залишиться
[23, 28, 32].
- Далі ми порівнюємо 23 з новим середнім елементом, 28.
- Оскільки 23 менше за 28, ми можемо виключити праву половину масиву:
[23].
- Ми знайшли шуканий елемент!
Обмеження
У стандартній бібліотеці Rust уже є функція бінарного пошуку.
У цій вправі не використовуйте цю функцію, натомість скористайтеся іншими базовими інструментами.
Для бонусних балів
Чи вдалося пройти тести й зробити код чистим? Якщо є бажання, можна спробувати ще дещо.
- Наразі функція find, найімовірніше, працюватиме лише зі зрізами чисел,
але система типів Rust досить гнучка, щоб створити функцію find, яка
працює з усіма зрізами, елементи яких можна впорядкувати.
- Крім того, ця функція find може працювати не лише зі зрізами, а водночас
також і з Vec, і з Array.
Щоб запустити бонусні тести, приберіть атрибут #[ignore] і виконайте тести з
увімкненою можливістю generic, ось так:
$ cargo test --features generic
А потім поділіться своїми думками в коментарі до рішення. Чи зробив цей
експеримент код кращим? Гіршим? Чи дізналися ми з нього щось корисне?
