Квадрарний пошук
Тернарний (або трійковий) пошук- це алгоритм пошуку мінімуму (або максимуму)опуклоюфункції на відрізку. Можна шукати мінімум (максимум) функції від речового аргументу, можна мінімум (максимум) на масиві. Будемо, для певності шукати мінімум функції f(x).
Він багатьом знайомий, а для тих, хто не знає, розповім коротенько.
Тернарний пошук ось у чому. Нехай є рекурсивна функція search(L, R), яка на двох кінцях відрізка L, R визначає мінімум на орезке [L, R]. Якщо R - L f (B), то мінімум лежить на відрізку [A, R]. Інакше - на відрізку [L, B]. Відповідно до цього, можна рекурсивно запуститися від одного з відрізків [L, B] або [A, R]. Щоразу довжина області пошуку зменшується у півтора рази, отже мінімум на відрізку довжини X з точністю eps буде знайдено за час O(log(X/eps)).
А тут я хочу розповісти проквадрарний (або четверичний) пошук.
По суті це певна оптимізація тернарного пошуку. Як і в ньому, ми будемо рекурсивно обчислювати мінімум функції на проміжку L, R. Тільки тепер ми обчислюватимемо значення функції не в двох, а в трьох точках: A=(3L+R)/4, B=(L+R )/2 та C=(L+3R)/4. Подивимося, яке з цих значень у цих трьох точках найменше. Якщо ліве - то запускаємося рекурсивно на відрізку [L,B], якщо праве - на відрізку [B,R], а якщо середнє - то на відрізку [A,C]. Довжина відрізка завжди зменшується вдвічі. При цьому слід зауважити, що якщо f(A)
P.S. Перенесено до «Алгоритм» з особистого блогу.
А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише у полі «секретний пароль» запровадити «Хабр»