Этот метод, как и первый, наиболее часто используется в программировании. Данный подход означает разделение задачи на подзадачи, равные примерно по сложности, для того чтобы перейти к решению значительно более простых задач, чем первоначальная. Поиск нужного элемента в таблице является характерным примером такого алгоритма:
- проверить первый элемент;
- if заданный элемент не найден, then продолжить поиск среди оставшихся элементов.
Таким образом, задача разбивается на две части: проверку первого элемента и поиск среди оставшихся. Ясно, что такие алгоритмы не равнозначны по сложности. Модифицированный алгоритм — двоичный поиск — имеет вид:
- проверить первый элемент;
- if заданный элемент не найден, then продолжить поиск в верхней или нижней половине списка.
В этом случае задача разбивается на две части, примерно одинаковые по сложности. Каждая из частей может иметь рекурсивное решение.