Алгоритм деления пополам

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

Поиск записи в последовательном массиве (неупорядоченный).

1. Одноступенчатый поиск – простейший вид поиска в последовательном массиве (поиск по совпадению).

Заданное значение х сравнивается с ключом первой записи а(i), если значения не совпадают с ключом второй записи и т.д. пока х не станет равным ключу очередной записи а(i).

Алгоритм очень прост, но время обработки в значительной степени зависит от n – числа элементов.

Число сравнений С определяется формулой С=М+1/2, где М – количество записей (номеров ключей).

Алгоритм поиска, когда элементы множества (ключи) расположены в произвольном порядке. Элементы множества: 1; 2; 3; 9; 5; 6; 7. Найти элемент множества значение которого равно 9, т.е. запись, ключ которой равен 9.

Form1 – 1

Const n = 7

Dim x As Integer

Private Sub Command1_Click ()

x = 9

a(1) = 1: a(2) = 2: a(3) = 3: a(4) = 9: a(5) = 5: a(6) = 6: a(7) = 7

For I = 1 To n

If a(i) = x Then

Debug.Print “a (“; i; “)=”; a(i)

End If

Next

End Sub

Res: a(4)=9

т.е. в четвертой ячейке находится 9-ая запись

2. Двухступенчатый поиск в массиве – этот метод предполагает упорядоченность обрабатываемых данных (блочный поиск).

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

Таким образом записи группируются в блоки и каждый блок проверяется по одному разу, пока не будет найден нужный блок.

Среднее число сравнений составит: С=М/2d₁ + d₁/2

Определим d₁ – размер блока, минимизирующий С

С=0; М/2d₁² + 1/2=0; d₁=

В файле из 10000 записей можно было бы использовать блоки содержащие 100 записей, прежде чем будет найдена искомая запись.

Использование этого метода для поиска записи последовательного файла из 10000 записей маловероятно. Этот метод используется при поиске в индексе.

Существует n-ступенчатый поиск.

Если значения элементов номеров записей множества упорядочены, то возможен более эффективный (быстрый) поиск.

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

Выбирается средний элемент этой последовательности и его значение а(i) сравнивается с искомым значением х. Если а(i) = х, то элемент множества найден и поиск закончен.

Если значения х окажется больше значения выбранного элемента, то исследуется та половина элементов последовательности, значения которых больше значения выбранного элемента а(i).

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

При повторении данной операции в итоге наступает момент, когда длина участка (d - c) становится равной одному элементу.

Данная программа имеет вид:

Form1 – 1

Const n = 7

Dim x As Integer, с As Integer, d As Integer, i As Integer

Dim a (1 To n) As Integer

Private Sub Command1_Click ()

x = 9: с = 1: d = n

a(1) = 1: a(2) = 2: a(3) = 3: a(4) = 5: a(5) = 6: a(6) = 9: a(7) = 10

Do

i = Int ((с + d)/2) int – целая часть (дробная отбрасывается)

If a(i) < x Then

c = i – 1

Else

If a(i) > x Then

d = i - 1

End If

End If

Loop White a(i) <> x

Debug.Print “a(“; i; “)=”; a(i)

End Sub

При х=9 Res a(6)=9

При х=1 Res a(1)=1

При х=10 Res a(7)=10

Если ввести значение ключа, которого нет в заданном массиве, то программа должна выдавать сообщение «Такого значения нет».

2-й учебный вопрос: списковая организация данных. (ценная или определенная структура).

Списковая организация данных это такая организация, при которой записи находятся не в последовательных адресах памяти, а расположены в произвольных местах. При этом необходимо связать в логическую последовательность с помощью специальных указателей или их еще называют адресов связи. Указатель – поле в одной записи, указывающее на место расположения второй записи. В записи А имеется указатель на запись С. Благодаря программному обеспечению, используемому при выборке записей цепь (список) представляется прикладному программисту в виде логической последовательности записей.

Рис. 1.

Рис. 2.

Возможны два способа организации списка:

1. Совместное размещение самой записи и указателей (адресов связи)(рис 1).

2. Раздельное из размещение, когда имеется списковая организация адресов связи и хранение собственно записей (рис 2).

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

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

Представленный на рисунке А список называется однонаправленным.

Списковая организация данных удобна в том случае, когда по тем или иным причинам нежелательна перезапись поступающих данных (как они расположились ранее в памяти, так там и находятся). Чтобы обрабатывать их в упорядоченной последовательности, все записи надо снабдить указателями и с их помощью определить цепочку записей, в которой значения ключевых реквизитов возрастают.

Для поиска данных в однонаправленном списке используется единственный метод – последовательный поиск.

Часто требуется осуществить поиск не по первичному(уникальному) а по вторичному, то есть ключу, который идентифицирует не уникальную запись, а все записи, имеющие определенное свойство (цвет глаз, например).

Дата добавления: 2014-01-04