Главная » 1С Предприятие » БИНАРНЫЙ ПОИСК

0

Методы   поиска  в   отсортированных   таблицах  указателей  основаны   на  алгоритме бинарного  поиска.

Пусть  упорядоченный массив х из п элементов содержит значения

5  7   11   18  26  32  44  57  81   90  94  97   107   116   129   147   179 и пусть  задан  аргумент  поиска ключ,  равный, например, 129.

Идея алгоритма бинарного поиска такова:

•    сравнить аргумент  поиска ключ  со значением  среднего  элемента х[сред]  массива х,

где сред = [п/2], а [с] целая часть числа с;

•   если они равны, то поиск завершен, иначе, если ключ < х[сред], выполнить аналогичным   образом   поиск   в    позициях  массива  х,  предшествующих   позиции   сред, в  противном случае, если  ключ  > х[сред], выполнить  аналогичным образом поиск в позициях массива х, следующих за позицией сред.

Исключить  из дальнейшего рассмотрения часть  массива позволяет  тот факт,  что массив упорядочен.

Проиллюстрируем процесс бинарного поиска. Число элементов массива п = 17, тогда   [п/2] = 8.  Поэтому  первоначально  выполняется сравнение  сред  с  x 8 =57 . Так как  сред > x8, то  зона  поиска  на  следующем  шаге  ограничивается участком  от 9-го  элемента до  17-го.  Этот участок  состоит из девяти  элементов и его серединой является элемент х13   = 107 ([(9 + 17)/2]  =  13). Поскольку сред > x13 , то зона поиска ограничивается участком  от  14-го до  17-го  элемента. Его  серединой  является элемент  x15.   На  этом   процесс  поиска  завершен,  так  как  х15  = сред.  Отобразим на рис. 9.3 процесс поиска элемента ключ = 129, выделяя посредством  подчеркивания на каждом  шаге зоны  поиска.

Итерация 0

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179

Итерация 0

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179

Итерация  1

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179

Итерация 3

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179

Рис. 9.3. Пример дихотомии

Каждое  сравнение уменьшает число возможных  кандидатов в 2 раза.  Максимальное число шагов поиска будет в том случае, когда аргумент  поиска находится в начале  или  в конце  массива. В этом  случае  потребуется log2n + 1  итераций. Действительно, если число элементов в массиве равно п = 2т, ключ будет найден, когда нерассмотренным  останется только  один элемент, то есть через т шагов. В свою очередь, при заданном п имеем т = log2n. После анализа последнего элемента получаем  общее  число итераций log2n + 1. Поэтому вычислительная сложность бинарного  поиска составляет O(log2n).

Однако приведенный алгоритм не позволяет в общем  случае точно  решить задачу поиска, когда  файл  или массив  содержат  повторяющиеся  значения  ключей. Рассмотрим, например, массив

5  7  11  18  26  32  44  57  81  90  94  97  107  129  129  147  179

в  котором элемент (ключ)  129 содержится  2 раза.  Тогда, если  аргумент  поиска будет равен 129, алгоритм, как и прежде, укажет, что ключ находится в 15-й позиции, то есть будет найдено не первое, а второе значение ключа  129 (первое значение ключа расположено  в позиции   14). В ряде случаев эта ошибка принципиальна, тогда она устраняется в результате  очевидной модификации алгоритма бинарного поиска.

9.2.2.     СРАВНЕНИЕ  ПОСЛЕДОВАТЕЛЬНОГО И  БИНАРНОГО ПОИСКА

Пусть  файл,   в  котором  выполняется  поиск,  отсортирован и  содержит  1024  (210) элемента. В случае последовательного поиска наибольшее число итераций будет равно 1024, а бинарного 11. То есть разница в два порядка.

Сравним теперь  временные  затраты  на поиск в случае неотсортированного  файла.  При последовательном поиске максимальное  число итераций, разумеется, сохраняется. Бинарный  поиск неприменим. Выполним, однако, быструю сортировку файла.  В среднем  для  этого  потребуется  1024*log21024 = 10240  итераций. Далее  выполним бинарный поиск, на который будет затрачено  не более 11 итераций.

Приведенные цифры позволяют сделать вывод: если файл неотсортирован и в процессе вычислений задача поиска в файле  возникает сравнительно редко  (в нашем  примере не более 10 раз), то можно  применять последовательный поиск, в противном случае  более  целесообразно прежде  отсортировать файл  или  таблицу указателей и  при вычислениях применять бинарный поиск. Как правило, именно такой  подход используется на практике.

Источник: Бартеньев О. В. 1С:Предприятие:  программирование для  всех.  Базовые объекты и расчеты на одной дискете. М.: Диалог-МИФИ, 2005. 464 с.

По теме:

  • Комментарии