Дихотомический поиск
Cтраница 1
 |
Пример двоичного дерева. [1] |
Дихотомический поиск особенно удобен в том случае, если таблица сначала составляется, а затем многократно используется. Если же приходится часто производить не только поиск, но и занесение новых записей, то эффективность работы снижается, так как для занесения новой ключевой записи в монотонно возрастающую по ключам последовательность в массиве S потребуется произвести раздвижку этой последовательности. При такой раздвижке потребуется - Л / операций перемещения помимо тех - logs N операций, которые будут затрачены на дихотомический поиск места в массиве S, куда нужно вставить новую ключевую запись. Преимущество раздельного хранения информации в массивах S к Т состоит в том, что при разд-движке ключевых записей в массиве S нет надобности перемещать тексты записей в массиве Т, поскольку порядок следования этих текстов записей не имеет значения. [2]
Дихотомический поиск - это метод поиска, позволяющий после каждой проверки уменьшать размер области поиска примерно в два раза. Для его осуществления необходимо помимо проверки выполнения условия поиска определить знак отклонения от заданного условия поиска. [3]
Дихотомический поиск удобно использовать для последовательно-смежной организации массива, если он предварительно упорядочен таким образом, что адреса объектов, записанных друг за другом, представляют собой монотонную функцию от признака, по которому осуществляется поиск. [4]
Дихотомический поиск узловой точки, соответствующей заданным значениям аргументов х и х2, может быть выполнен в два этапа. [5]
Процедура дихотомического поиска в массиве должна начинаться с проверки всегда одного и того же элемента, расположенного в середине массива. Адрес этого элемента всегда может быть вычислен, если известно положение границ массива. В списке, организованном с помощью слов связи, нет возможности вычислить адрес этого элемента, и поэтому он должен быть явно указан в некоторой специально отведенной для этой цели ячейке. [6]
На любом шаге дихотомического поиска в массиве по результатам проверки условия поиска в некотором элементе производится выбор одного из двух других элементов массива для выполнения в них следующей проверки условия поиска. Адреса этих элементов всегда могут быть вычислены, если известны границы зоны поиска и адрес последнего из проверявшихся элементов. [7]
Для возможности осуществления дихотомического поиска существенно, чтобы, кроме понятия выполнения или невыполнения условия поиска в том или ином объекте, было определено понятие о знаке отклонения от заданного условия поиска в тех случаях, когда оно не выполняется. В случае поиска по совпадению или близости отклонение считается положительным, если признак, соответствующий рассматриваемому объекту, больше заданного числа или ключа, интерпретируемого как число, и отрицательным, если признак оказывается меньше заданного числа или ключа. В случае поиска по интервалу отклонение считается положительным, если признак, соответствующий проверяемому объекту, больше верхней границы заданного интервала, и отрицательным, если признак меньше нижней границы интервала. Организация множества объектов в памяти должна позволять после каждой проверки выполнения условия поиска в случае выявленного положительного отклонения сразу же исключать из подмножества неопределенности объекты с еще большими положительными отклонениями, а в случае выявленного отрицательного отклонения - объекты с еще большими по абсолютной величине отрицательными отклонениями. [8]
На втором этапе осуществляется дихотомический поиск по близости к числу, сформированному в виде л 1узл в старших разрядах и х2 в младших разрядах. [9]
Цепная организация массива не приспособлена для дихотомического поиска. Для него удобна ветвящаяся структура с двумя адресами связи, исходящими от каждого объекта. Через один из этих адресов связи каждый объект связывается с подмножеством объектов, признак которых больше ( или не меньше), чем у этого объекта, а через другой адрес связи с группой объектов, у которых признак меньше ( или не больше), чем у исходного объекта. В результате проверки знака отклонения одно из подмножеств исключается из дальнейшего поиска. [10]
Существует много различных способов поиска записей, например блочный и дихотомический поиск. Наиболее простым способом является последовательное сканирование с проверкой ключа каждой записи. [11]
Иногда бывает целесообразно провести лишь несколько шагов дихотомического поиска и перейти затем к другому виду поиска. Такой поиск удобно описывать с помощью деревьев. [12]
На рис. 1.8 изображена блок-схема еще одного варианта дихотомического поиска по совпадению или интервалу. [13]
Для каждой вершины х, х г, составляют таблицу для ведения дихотомического поиска вплоть до R - ro этажа. [14]
Множество объектов, организованное в памяти в виде цепочки, не приспособлено для дихотомического поиска. Структура же двоичного дерева с двумя адресами связи, исходящими от каждого объекта, весьма удобна для организации дихотомического поиска. Через один из этих адресов связи каждый объект связывается с группой объектов, признак которых больше ( или по крайней мере не меньше), чем у этого объекта, а через другой адрес связи - с группой объектов, у которых признак меньше ( или по крайней мере не больше), чем у исходного объекта. В результате проверки знака отклонения от условия поиска одна из групп исключается из подмножества неопределенности и, следовательно, из дальнейшего поиска. [15]
Страницы: 1 2