Подразделы

Другие разделы

Дата и время

06/01/2026 16:46:04

Авторизация

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

Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы

Бинарный поиск

Бинарный поиск -- это эффективный алгоритм
для поиска в отсортированном массиве. Он работает путем сравнения искомого
ключа `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. Напишите псевдокод рекурсивной версии бинарного поиска.

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

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

Бинарный поиск