Тема 9 Алгоритмы поиска и перебора
9.1. Поиск. Основные понятия
С задачами поиска информации человеку приходиться сталкиваться постоянно. Типичными примерами служит поиск по справочникам, телефонной книге, картотеке и т.д. Полагаем, что файл состоит из записей с ключами и пусть K – значение ключа. Различают четыре варианта простейших задач.
1). Требуется определить, по крайней мере, одну запись из -файла, имеющую своим ключом K.
2). Определить все записи из -файла, имеющие K своим ключом.
3). Если в -файле нет записей с ключом K, то добавить новую запись.
4). Включить в -файл новую запись.
K называется аргументом поиска или
запросом, первые две задачи простым
статическим поиском, а последние две –
динамическим поиском со вставкой. Иногда
в трех первых задачах поиск организуется
не по ключу, а по выполнению некоторых
условий для определенной функции от
ключей. Примером может служить поиск
по интервалу значений ключа, когда
отыскиваются записи
с условиями:
,
где a и b
– константы. Методы поиска классифицируются
по местонахождению и изменению -файла,
схеме доступа к отдельным записям
,
способу сравнения ключей или функций
от них и т.п. Например, поиск называется
внутренним, если -файл
целиком размещается в оперативной
памяти, и внешним – в противном случае.
Здесь мы будем рассматривать только
внутренний поиск. Под файлом будем
понимать одномерный или двумерный
числовой или символьный массив, и поиск
вести в одномерной или двумерной таблице.
Различные варианты задач поиска встречаются при решении других проблем, например, в сортировках, где постоянно приходиться искать пары для текущих обменов. От организации исходной информации во многом зависит эффективность алгоритмов поиска. И в этом контексте сортировки играют полезную роль в предварительном преобразовании -файла. В различных информационных системах поиск требует наибольших временных затрат. Поэтому эффективность их программного обеспечения прямо зависит от типа используемого алгоритма поиска.
9.2. Бинарный поиск
Н
Dim S() As
Integer: Const n As Integer = 10, K As Integer = 11 Sub
Бинарный_поиск()
'Отладочный вариант
Dim i As
Integer, a As Integer, b As Integer, var As String
ReDim S(1
To n): S(1)=2: S(2)=7: S(3)=8: S(4)=9: S(5)=13: S(6)=15: S(7)=16:
S(8)=17: S(9)=18: S(10)=23
var =
"Исходные:": For j = 1 To n: var = var & "
" & Str(S(j)): Next j: MsgBox var: a = 1: b = n: 1:
If b <a Then
MsgBox
"Неудача":
Exit Sub Else i
= (a + b)\2
If K =
S(i) Then: MsgBox "Адрес:
" & Str(i) & ". Значение:
" & Str(S(i)) & ". Ключ:
" & Str(K): Exit Sub
Else: If K
< S(i) Then: b = i – 1: Else: a = i + 1: End If End
If GoTo
1 End
If End
Sub