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

Алгоритм бинарного поиска является одним из наиболее эффективных алгоритмов поиска в упорядоченном массиве. Упрощенно этот алгоритм состоит в следующем. Аргумент поиска сравнивается со средним элементом массива. Если они равны, то поиск успешно заканчивается. В противном случае поиск аналогичным образом должен быть осуществлен в верхней или нижней половине массива [3, 6].

Алгоритм бинарного поиска

Пусть имеется массив, значения которого упорядочены по возрастанию, то есть К1 <Кг <...<Кп. Необходимо найти элемент массива, равный заданному аргументу поиска К.

  • 1. L = 1. Левая граница массива.
  • 2. R = п. Правая граница массива.
  • 3. Если R < L, то алгоритм заканчивается неудачно.
  • 4. i = L(L + R)/2_|.
  • 5. Если К = Ki, алгоритм заканчивается успешно.
  • 6. Иначе если К < Ki, то R = i - 1. Перейти на шаг 3.
  • 7. Иначе (К > Kj) L = i + 1. Перейти на шаг 3.

Алгоритм оптимального бинарного поиска

Приведенный выше алгоритм в случае успешного поиска позволяет найти элемент в среднем за log2(N+l)-1 сравнений. При неудачном поиске требуется log2(N+l) сравнений, то есть в среднем удачный поиск отличается от неудачного только на одно сравнение.

Основываясь на этом факте можно упростить алгоритм бинарного поиска, убрав из цикла (шаг 5) проверку на равенство К = Ki. Так как в цикле найти ключ будет невозможно, то цикл будет выполняться максимальное число раз (до пересечения границ). Таким образом, цикл будет выполняться log2(N+l) раз, и именно столько раз не будет выполняться данная проверка. Отсюда, выигрыш такого предложения можно оценить как log2(N+l) сравнений.

Как было отмечено выше, в среднем удачный поиск отличается от неудачного только на одно сравнение. Следовательно, отсутствие шага 5 приведет к тому, что в цикле добавляется в среднем одна итерация или два дополнительных сравнения.

Кроме того, необходимо выполнить одно сравнение после цикла, проверяющее наличие искомого элемента на пересечении левой и правой границы массива. Тогда общий выигрыш такого подхода определяется как

Тогда алгоритм оптимального бинарного поиска будет состоять из следующих шагов [7].

  • 1. L = 1. Левая граница массива.
  • 2. R = п. Правая граница массива.
  • 3. Если R <= L, то перейти на шаг 7.
  • 4. i = L(L + R)/2_|.
  • 5. Если К <= Ki, то R = i. Перейти на шаг 3.
  • 6. Иначе (К > КО L = i + 1. Перейти на шаг 3.
  • 7. Если KR = К, то поиск удачен. Иначе элемента нет в массиве.

Алгоритм оптимального бинарного поиска имеет те же характеристики,

что и алгоритм неоптимального бинарного поиска, то есть сложность данных алгоритмов оценивается как 0[log2(N)].

У бинарного поиска есть ряд недостатков, вытекающих из необходимости поддерживать упорядоченность массива. Чтобы вставить новую запись в существующую таблицу для сохранения упорядоченности потребуется перенести в среднем N/2 записей. Подобная ситуация возникает и при удалении записей.

Поэтому бинарный поиск удобен только при небольшом числе вставок и/или удалений записей из таблицы.

Одним из путей улучшения этого метода поиска является использование для представления таблиц бинарных деревьев поиска, что значительно облегчает задачу вставки и удаления записей.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >