Метод бинарного поиска

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

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

Метод (алгоритм) бинарного поиска реализуется следующим образом:

1. Сначала образец сравнивается со средним (по номеру) элементом массива (рис. 5.10, а).

• Если образец равен среднему элементу, то задача решена.
• Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verb принимается sred+i, а значение niz не меняется (рис. 5.10, б).
• Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется (рис. 5.10, в).

a

б

в

Рис. 5.10. Выбор среднего элемента массива при бинарном поиске

Рис. 5.11. Алгоритм бинарного поиска в упорядоченном по возрастанию массиве

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.

Алгоритм бинарного поиска, блок-схема которого представлена на рис. 5.11, заканчивает свою работу, если искомый элемент найден или если перед выполнением очередного цикла поиска обнаруживается, что значение verh больше, чем niz.

Вид диалогового окна программы Бинарный поиск в массиве приведен на рис. 5.12. Поле метки Label3 используется для вывода результатов поиска и протокола поиска. Протокол поиска выводится, если установлен флажок выводить протокол. Протокол содержит значения переменных verh, niz, sred. Эта информация, выводимая во время поиска, полезна для понимания сути алгоритма.

Рис. 5.12. Диалоговое окно программы Бинарный поиск в массиве

В форме приложения появился новый компонент, который до этого момента в программах не использовался, — флажок (компонент CheckBox). Значок компонента checkBox находится на вкладке Standard (рис. 5.13). Добавляется к форме он точно так же, как и другие компоненты. Свойства компонента CheckBox перечислены в табл. 5.5.

Таблица 5.5. Свойства компонента CheckBox

	Свойство	Определяет
	Name	Имя компонента. Используется в программе для доступа к свойствам компонента
	Caption	Текст, поясняющий назначение флажка
	Checked	Состояние, внешний вид флажка: если флажок установлен (в квадратике есть "галочка"), то checked = TRUE; если флажок сброшен (нет "галочки"), то Checked=FALSE
	State	Состояние флажка. В отличие от свойства Checked, позволяет различать установленное, сброшенное и промежуточное состояния. Состояние флажка определяют константы: cbChecked (установлен); cbGrayed (серый, неопределенное состояние); cbUnChecked (сброшен)
	AllowGrayed	Может ли флажок быть в промежуточном состоянии: если AllowGrayed = FALSE, то флажок может быть только установленным или сброшенным; если AllowGrayed = TRUE, то допустимо промежуточное состояние

	Свойство	Определяет
	Left Top Height Width Font ParentFont	Расстояние от левой границы флажка до левой границы формы Расстояние от верхней границы флажка до верхней границы формы Высоту поля вывода поясняющего текста Ширину поля вывода поясняющего текста Шрифт, используемый для отображения поясняющего текста Признак наследования характеристик шрифта родительской формы

Рис. 5.13. Компонент CheckBox

После того как компонент CheckBox будет добавлен к форме, а добавляется он обычным образом, нужно установить значения его свойств в соответствии с табл. 5.6.

Таблица 5.6. Значения свойств компонента CheckBox1

	Свойство	Значение
	Caption Checked	Выводить протокол True

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

При вычислении номера среднего элемента используется функция тгипс, которая округляет до ближайшего целого и преобразует к типу integer выражение, полученное в качестве аргумента. Необходимость использования тгипс объясняется тем, что выражение (niz-verh) /2 — дробного типа, переменная sred — целого, а переменной целого типа присвоить дробное значение нельзя (компилятор выдаст сообщение об ошибке).

Обратите внимание на процедуры обработки события onKeyPress для компонентов stringGrid1 и Edit1. Первая из них обеспечивает перемещение курсора в следующую ячейку таблицы или в поле Edit1 (из последней ячейки) в результате нажатия клавиши <Enter>, вторая — активизирует командную кнопку Поиск также в результате нажатия клавиши <Enter>.