Вступ
Ми натрапили на групу математиків, які водночас є авторами-виконавцями.
Вони написали пісню про кожне зі своїх улюблених чисел, а улюблених чисел у них, як можна уявити, багато (наприклад, 0 чи 73, або 6174).
Нам цікаво почути пісню про своє улюблене число, але через таку кількість пісень, які треба перебрати, пошук потрібної може зайняти чимало часу.
На щастя, вони впорядкували свої пісні в плейлист, відсортований за назвою, а назва - це просто число, якому присвячено пісню.
Ми розуміємо, що можемо скористатися алгоритмом двійкового пошуку, щоб швидко знайти пісню за назвою.
Вказівки
Наше завдання - реалізувати алгоритм двійкового пошуку.
Алгоритм двійкового пошуку знаходить елемент у масиві, раз за разом ділячи його навпіл і зберігаючи лише ту половину, яка містить шуканий елемент.
Це дає змогу швидко звужувати коло можливих місць розташування шуканого елемента, доки ми його не знайдемо або доки не виключимо всі можливі місця.
Двійковий пошук працює лише тоді, коли масив відсортовано.
Алгоритм має такий вигляд:
- Знайти середній елемент відсортованого масиву і порівняти його з шуканим елементом.
- Якщо середній елемент збігається з шуканим, ми закінчили!
- Якщо середній елемент більший за шуканий, ми можемо виключити цей елемент і всі елементи після нього.
- Якщо середній елемент менший за шуканий, ми можемо виключити цей елемент і всі елементи перед ним.
- Якщо виключено всі елементи масиву, то шуканого елемента в масиві немає.
- Інакше повторімо процес на тій частині масиву, яку ще не виключено.
Ось приклад:
Припустімо, ми шукаємо число 23 у такому відсортованому масиві: [4, 8, 12, 16, 23, 28, 32].
- Спочатку ми порівнюємо 23 із середнім елементом, 16.
- Оскільки 23 більше за 16, ми можемо виключити ліву половину масиву, і в нас залишиться
[23, 28, 32].
- Далі ми порівнюємо 23 з новим середнім елементом, 28.
- Оскільки 23 менше за 28, ми можемо виключити праву половину масиву:
[23].
- Ми знайшли шуканий елемент!
Поведінка
Рішення має відповідати поведінці вбудованих функцій searchsorted у Julia для тестових випадків.
Це означає, що замість індексу першого відповідного елемента, який ми знайдемо в масиві, ми повертаємо діапазон, нижня межа якого - індекс першого відповідного елемента в масиві, а верхня межа - індекс останнього відповідного елемента в масиві.
Однак для спрощення рішення ми можемо припустити, що цільовий елемент не повторюється, крім набору тестів бонусного завдання про кілька збігів.
Якщо шуканого елемента немає в масиві, потрібно повернути порожній діапазон, нижня межа якого - індекс, за яким елемент можна було б вставити у відсортований масив. Порожній діапазон - це будь-який діапазон, у якому верхня межа менша за нижню.
Щоб дізнатися більше, прочитаймо документацію та приклади для функції searchsorted:
searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)
Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.
See also: insorted, searchsortedfirst, sort, findall.
Examples
julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3
julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5
julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2
julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6
julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0
Бонусні завдання
- Розширте рішення, щоб воно підтримувало ключові аргументи
by, lt і rev: by задає
перетворення, застосоване до всіх елементів масиву, lt задає
порівняння, а rev вказує, чи впорядковано масив у зворотному порядку. Коли ці
параметри використано, потрібно припустити, що масив уже відсортовано
за цими параметрами. Докладніше дивіться в документації до sort.
- Підтримайте масиви, у яких цільовий елемент повторюється (знайдіть перший і останній індекс, за яким цільовий елемент вважається рівним).
