Алгоритм

Берем средний элемент массива (обозначим его номер M) и сравниваем его с ключом. Возможны три исхода:

1) если средний элемент массива равен ключу, то искомый элемент найден;

2) если средний элемент массива меньше ключа, то все элементы массива с индексами, которые меньше M исключаются из рассмотрения;

3) если элемент массива больше ключа, то все элементы массива с индексами, которые больше M исключаются из рассмотрения;

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

1. Начальная установка: L = 1, R = N

2. Если R < L, то алгоритм окончен неудачно и перейти к шагу 7

3., в противном случае находим середину интервала [L; R] (M = (L+R)/2)

4. Если b<A[M], то перейти к шагу 5, если b>A[M], то перейти к шагу 6, если b=A[M], то алгоритм окончен удачно и перейти к шагу 7

5. Установить R=M-1, перейти к шагу 2

6. Установить L=M+1, перейти к шагу 2

7. Конец

Нахождение элемента бинарным поиском осуществляется очень быстро. При поиске среди N элементов требуется log₂(N) сравнений в наихудшем случае. Кроме того, бинарный поиск уже при N порядка 100 значительно эффективнее линейного – как по скорости обнаружения, так и по способности к получению отрицательного результата. Для доказательства этого приведем следующие характеристики линейного и бинарного поиска:

поиск	количество элементов	среднее количество сравнений при наличии элемента	количество сравнений при отсутствии элемента
линейный
линейный
линейный
бинарный
бинарный
бинарный

Алгоритмы поиска минимума (максимума)

Дата добавления: 2015-07-12