Алгоритми та структури даних · Middle · Запитання 16 з 75
Як знайти значення у відсортованому масиві, який повернули циклічно, наприклад [4, 5, 6, 1, 2, 3], за O(log n)?
- 1Лінійним пошуком, бо поворот ламає порядок
- ✓Правильна відповідь: Бінарним пошуком, щокроку визначаючи, яка половина відсортована
- 3Спершу відсортувати масив, потім звичайний бінарний пошук
Пояснення
Порівняйте arr[lo] з arr[mid], щоб зрозуміти, яка половина впорядкована, а потім перевірте, чи потрапляє ціль у її діапазон. Сортування спершу коштує O(n log n), лінійний пошук O(n).