При выполнении линейного (linear) поиска или поиска методом полного перебора (exhaustive search), поиск ведется с начала списка, и элементы перебираются последовательно, пока среди них не будет найден искомый.
Public Function LinearSearch(target As Long) As Long
Dim i As Long
For i = 1 To NumItems
If List(i) >= target Then Exit For
Next i
If i > NumItems Then
Search = 0 ' Элемент не найден.
Else
Search = i ' Элемент найден.
End If
End Function
Так как этот алгоритм проверяет элементы последовательно, то он находит элементы в начале списка быстрее, чем элементы, расположенные в конце. Наихудший случай для этого алгоритма возникает, если элемент находится в конце списка или вообще не присутствует в нем. В этих случаях, алгоритм проверяет все элементы в списке, поэтому время его выполнения сложность в наихудшем случае порядка O(N).
@Рис. 10.1. Программа Search
========266
Если элемент находится в списке, то в среднем алгоритм проверяет N/2 элементов до того, как обнаружит искомый. Таким образом, в усредненном случае время выполнения алгоритма также порядка O(N).
Хотя алгоритмы, которые выполняются за время порядка O(N), не являются очень быстрыми, этот алгоритм достаточно прост, чтобы давать на практике неплохие результаты. Для небольших списков этот алгоритм имеет приемлемую производительность.
Если список упорядочен, то можно слегка модифицировать алгоритм полного перебора, чтобы немного повысить его производительность. В этом случае, если во время выполнения поиска алгоритм находит элемент со значением, большим, чем значение искомого элемента, то он завершает свою работу. При этом искомый элемент не находится в списке, так как иначе он бы встретился раньше.
Например, предположим, что мы ищем значение 12 и дошли до значения 17. При этом мы уже прошли тот участок списка, в котором мог бы находится элемент со значением 12, значит, элемент 12 в списке отсутствует. Следующий код демонстрирует доработанную версию алгоритма поиска полным перебором:
Public Function LinearSearch(target As Long) As Long
Dim i As Long
NumSearches = 0
For i = 1 To NumItems
NumSearches = NumSearches + 1
If List(i) >= target Then Exit For
Next i
If i > NumItems Then
LinearSearch = 0 ' Элемент не найден.
ElseIf List(i) <> target Then
LinearSearch = 0 ' Элемент не найден.
Else
LinearSearch = i ' Элемент найден.
End If
End Function
Эта модификация уменьшает время выполнения алгоритма, если элемент отсутствует в списке. Предыдущей версии поиска требовалось проверить весь список до конца, если искомого элемента в нем не было. Новая версия остановится, как только обнаружит элемент больший, чем искомый.
Если искомый элемент расположен случайно между наибольшим и наименьшим элементами в списке, то в среднем алгоритму понадобится порядка O(N) шагов, чтобы определить, что искомый элемент отсутствует в списке. Время выполнения при этом имеет тот же порядок, но на практике его производительность будет немного выше. Программа Search использует эту версию алгоритма.
======267
Поиск методом полного перебора — это единственный способ поиска в связных списках. Так как доступ к элементам возможен только при помощи указателей NextCell на следующий элемент, то необходимо проверить по очереди все элементы с начала списка, чтобы найти искомый.
Так же, как и в случае поиска полным перебором в массиве, если список упорядочен, то можно прекратить поиск, если найдется элемент со значением, большим, чем значение искомого элемента.
Public Function LListSearch(target As Long) As SearchCell
Dim cell As SearchCell
NumSearches = 0
Set cell = ListTop.NextCell
Do While Not (cell Is Nothing)
NumSearches = NumSearches + 1
If cell.Value >= target Then Exit Do
Set cell = cell.NextCell
Loop
If Not (cell Is Nothing) Then
If cell.Value = target Then
Set LListSearch = cell ' Элемент найден.
End If
End If
End Function
Программа Search использует этот алгоритм для поиска элементов в связном списке. Этот алгоритм выполняется немного медленнее, чем алгоритм полного перебора в массиве из‑за дополнительных накладных расходов, которые связаны с управлением указателями на объекты. Заметьте, что программа Search строит связные списки, только если список содержит не более 10.000 элементов.
Чтобы алгоритм выполнялся немного быстрее, в него можно внести еще одно изменение. Если хранить указатель на конец списка, то можно добавить в конец списка ячейку, которая будет содержать искомый элемент. Этот элемент называется сигнальной меткой (sentinel), и служит для тех же целей, что и сигнальные метки, описанные во 2 главе. Это позволяет обрабатывать особый случай конца списка так же, как и все остальные.
В этом случае, добавление метки в конец списка гарантирует, что в конце концов искомый элемент будет найден. При этом программа не может выйти за конец списка, и нет необходимости проверять условие Not (cell Is Nothing) в каждом цикле While.
Public Function SentinelSearch(target As Long) As SearchCell
Dim cell As SearchCell
Dim sentinel As New SearchCell
NumSearches = 0
' Установить сигнальную метку.
sentinel.Value = target
Set ListBottom.NextCell = sentinel
' Найти искомый элемент.
Set cell = ListTop.NextCell
Do While cell.Value < target
NumSearches = NumSearches + 1
Set cell = cell.NextCell
Loop
' Определить найден ли искомый элемент.
If Not ((cell Is sentinel) Or _
(cell.Value <> target)) _
Then
Set SentinelSearch = cell ' Элемент найден.
End If
' Удалить сигнальную метку.
Set ListBottom.NextCell = Nothing
End Function
Хотя может показаться, что это изменение незначительно, проверка Not (cell Is Nothing) выполняется в цикле, который вызывается очень часто. Для больших списков этот цикл вызывается множество раз, и выигрыш времени суммируется. В Visual Basic, этот версия алгоритма поиска в связных списках выполняется на 20 процентов быстрее, чем предыдущая версия. В программе Search приведены обе версии этого алгоритма, и вы можете сравнить их.
Некоторые алгоритмы используют потоки для ускорения поиска в связных списках. Например, при помощи указателей в ячейках списка можно организовать список в виде двоичного дерева. Поиск элемента с использованием этого дерева займет время порядка O(log(N)), если дерево сбалансировано. Такие структуры данных уже не являются просто списками, поэтому мы не обсуждаем их в этой главе. Чтобы больше узнать о деревьях, обратитесь к 6 и 7 главам
Как уже упоминалось в предыдущих разделах, поиск полным перебором выполняется очень быстро для небольших списков, но для больших списков намного быстрее выполняется двоичный поиск. Алгоритм двоичного поиска (binary search) сравнивает элемент в середине списка с искомым. Если искомый элемент меньше, чем найденный, то алгоритм продолжает поиск в первой половине списка, если больше — в правой половине. На рис. 10.2 этот процесс изображен графически.
Хотя по своей природе этот алгоритм является рекурсивным, его достаточно просто записать и без применения рекурсии. Так как этот алгоритм прост для понимания в любом варианте (с рекурсией или без), то мы приводим здесь его нерекурсивную версию, которая содержит меньше вызовов функций.
Основная заключенная в этом алгоритме идея проста, но детали ее реализации достаточно сложны. Программе приходится аккуратно отслеживать часть массива, которая может содержать искомый элемент, иначе она может его пропустить.
Алгоритм использует две переменные, min и max, в которых находятся минимальный и максимальный индексы ячеек массива, которые могут содержать искомый элемент. Во время выполнения алгоритма, индекс искомой ячейки всегда будет лежать между min и max. Другими словами, min <= target index <= max.
==========269
@Рис. 10.2. Двоичный поиск элемента со значением 44
Во время каждого прохода, алгоритм выполняет присвоение middle = (min + max) / 2 и проверяет ячейку, индекс которой равен middle. Если ее значение равно искомому, то цель найдена и алгоритм завершает свою работу.
Если значение искомого элемента меньше, чем значение среднего, то алгоритм устанавливает значение переменной max равным middle – 1 и продолжает поиск. Так как теперь индексы элементов, которые могут содержать искомый элемент, находятся в диапазоне от min до middle – 1, то программа при этом выполняет поиск в первой половине списка.
В конце концов, программа либо найдет искомый элемент, либо наступит момент, когда значение переменной min станет больше, чем значение max. Поскольку индекс искомого элемента должен находиться между минимальным и максимальным возможными индексами, это означает, что искомый элемент отсутствует в списке.
Следующий код демонстрирует выполнение двоичного поиска в программе Search:
Public Function BinarySearch(target As Long) As Long
Dim min As Long
Dim max As Long
Dim middle As Long
NumSearches = 0
' Во время поиска индекс искомого элемента будет находиться
' между Min и Max: Min <= target index <= Max
min = 1
max = NumItems
Do While min <= max
NumSearches = NumSearches + 1
middle = (max + min) / 2
If target = List(middle) Then ' Мы нашли искомый элемент!
BinarySearch = middle
Exit Function
ElseIf target < List(middle) Then ' Поиск в левой половине.
max = middle - 1
Else ' Поиск в правой половине.
min = middle + 1
End If
Loop
' Если мы оказались здесь, то искомого элемента нет в списке.
BinarySearch = 0
End Function
На каждом шаге число элементов, которые еще могут иметь искомое значение, уменьшается вдвое. Для списка размера N, алгоритму может потребоваться максимум O(log(N)) шагов, чтобы найти любой элемент или определить, что его нет в списке. Это намного быстрее, чем в случае применения алгоритма полного перебора. Полный перебор списка из миллиона элементов потребовал бы в среднем 500.000 шагов. Алгоритму двоичного поиска потребуется не больше, чем log(1.000.000) или 20 шагов.
Двоичный поиск обеспечивает значительное увеличение скорости поиска по сравнению с полным перебором, так как он исключает большие части списка, не проверяя при этом значения исключаемых элементов. Если, кроме того, известно, что значения элементов распределены достаточно равномерно, то можно исключать на каждом шаге еще больше элементов, используя интерполяционный поиск (interpolation search).