Дихотомический поиск

Дихотомический поиск [dichotomic search] — 1. (В численных методах оптимизации) — поиск оптимума путем последовательного деления пополам (дихотомии) пространства решений и проверки каждой половины на наличие в ней экстремальной точки. Оптимум отыскивается таким путем за конечное количество шагов (делений).

2. Поиск информации в любом массиве данных путем его последовательного дихотомического деления. Искомая информация находится за [log2N]+1 шагов[1], где N — число данных в исходном массиве. (Названный выше метод оптимизации — частный случай по отношению к 2).

 


[1] Квадратные скобки означают здесь выделение наибольшего целого числа, не превышающего результат логарифмирования.