Методы уменьшения размера задачи

Бинарный поиск – это эффективный алгоритм для поиска в отсортированном массиве. Он работает путем сравнения искомого ключа `K` со средним элементом массива `A[m]`. Если они равны, алгоритм прекращает работу. В противном случае та же операция рекурсивно повторяется для первой половины массива, если `K < A [m]`, и для второй, если `K > A [m]`:

`ubrace(A_0 <= ... <= A_{m-1})_("Поиск в этой части, если "K<A_m) <= overset(overset(K)( = ?))(A_m) <= ubrace(A_{m+1} <= ... <= A_{n-1})_("Поиск в этой части, если "K>A_m)`

Хотя бинарный поиск основан на рекурсии, его очень легко реализовать как нерекурсивный алгоритм.

Алгоритм BinarySearch `(A, K)`
// Входные данные: Массив `A[0...n-1]`, отсортированный
// в возрастающем порядке, и искомый ключ `K`
// Выходные данные: Индекс элемента массива, равного `K`,
// или —1, если такого элемента нет
`l larr 0; r larr n -1`
while `l<=r` do
`quad m larr |__ (l+r)//2__|`
`quad` if `K =A[m]`
`quad quad quad` return `m`
`quad` else if `K < A[m]`
`quad quad quad r larr m - 1`
`quad` else
`quad quad quad l larr m + 1`
return -1

Основной операцией бинарного поиска является сравнение искомого ключа с элементами массива. При этом одно сравнение `K` и `A[m]` позволяет определить, меньше ли `K`, больше или равно значению `A[m]`.

В наихудший случай входят все массивы, которые не содержат искомого ключа. Поскольку после одного сравнения алгоритм попадает в ту же ситуацию, что и до сравнения, только массив, в котором ведется поиск, становится вдвое меньше, можно записать следующее рекуррентное соотношение:
`C_{"worst"}(n)=C_{"worst"}(|__n//2__|) + 1` при `n > 1`, `C_{"worst"}(1) = 1`.

Мы полагаем `n = 2^k` и решаем получившееся соотношение путем обратной подстановки:
`C_{"worst"}(2^k) = k + 1 = log_2 n + 1 in Theta(log n)`.

Количество сравнений в среднем случае только немного меньше такового в наихудшем случае: `C_{"avg"}(n) ~~ log_2 n`.

Задания для практики

1. Напишите псевдокод рекурсивной версии бинарного поиска.