На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде — по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод бинарного поиска.
Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).
Метод (алгоритм) бинарного поиска реализуется следующим образом:
1. Сначала образец сравнивается со средним (по номеру) элементом массива
- Если образец равен среднему элементу, то задача решена.
- Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verb принимается sred+i, а значение niz не меняется.
- Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется.
В форме приложения появился новый компонент, который до этого момента в программах не использовался, — флажок (компонент CheckBox). Значок компонента checkBox находится на вкладке Standard. Добавляется к форме он точно так же, как и другие компоненты.
Свойства компонента CheckBox
| Свойство | Определяет | ||
| Name | Имя компонента. Используется в программе для доступа к свойствам компонента | ||
| Caption | Текст, поясняющий назначение флажка | ||
| Checked | Состояние, внешний вид флажка: если флажок установлен (в квадратике есть «галочка»), то checked = TRUE; если флажок сброшен (нет «галочки»), то Checked=FALSE | ||
| State | Состояние флажка. В отличие от свойства Checked, позволяет различать установленное, сброшенное и промежуточное состояния. Состояние флажка определяют константы: cbChecked (установлен); cbGrayed (серый, неопределенное состояние); cbUnChecked (сброшен) | ||
| AllowGrayed | Может ли флажок быть в промежуточном состоянии: если AllowGrayed = FALSE, то флажок может быть только установленным или сброшенным; если AllowGrayed = TRUE, то допустимо промежуточное состояние | ||
| Свойство | Определяет | ||
| LeftTopHeightWidthFontParentFont | Расстояние от левой границы флажка до левой границы формыРасстояние от верхней границы флажка до верхней границы формыВысоту поля вывода поясняющего текстаШирину поля вывода поясняющего текстаШрифт, используемый для отображения поясняющего текстаПризнак наследования характеристик шрифта родительской формы | ||
После того как компонент CheckBox будет добавлен к форме, а добавляется он обычным образом, нужно установить значения его свойств
Значения свойств компонента CheckBox1
| Свойство | Значение | ||
| CaptionChecked | Выводить протокол True | ||
В листинге 5.8 приведен текст процедуры обработки события Onclick для командной кнопки Поиск (Button1). Процедура вводит значения элементов массива и образец, затем, используя алгоритм бинарного поиска, проверяет, содержит ли массив элемент, равный образцу. Кроме того, переменная п (число сравнений с образцом) позволяет оценить эффективность алгоритма бинарного поиска по сравнению с поиском методом простого перебора.
При вычислении номера среднего элемента используется функция тгипс, которая округляет до ближайшего целого и преобразует к типу integer выражение, полученное в качестве аргумента. Необходимость использования тгипс объясняется тем, что выражение (niz-verh) /2 — дробного типа, переменная sred — целого, а переменной целого типа присвоить дробное значение нельзя (компилятор выдаст сообщение об ошибке).
Обратите внимание на процедуры обработки события onKeyPress для компонентов stringGridl и Editl. Первая из них обеспечивает перемещение курсора в следующую ячейку таблицы или в поле Editl (из последней ячейки) в результате нажатия клавиши <Enter>, вторая — активизирует командную кнопку Поиск также в результате нажатия клавиши <Enter>.
Листинг. Бинарный поиск в массиве
found;
interface
uses
Windows, Messages, SysUtils, Classes,
Graphics, Controls, Forms, Dialogs, StdCtrls, Grids;
type
TForm1 = class(TForm)
Label1: TLabel;
Label2: TLabel;
Button1: TButton;
Label3: TLabel;
CheckBox1: TCheckBox;
StringGrid1: TStringGrid;
Editl: TEdit;
procedure ButtonlClick(Sender: TObject);
procedure StringGridlKeyPress(Sender: TObject; var Key: Char);
procedure EditlKeyPress(Sender: TObject; var Key: Char); private
{Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.DFM}
{ Бинарным поиск в массиве }
procedure TForm1.Button1Click(Sender: TObject);
const
SIZE=10; var
a:array[1..SIZE] of integer; { массив )
obr:integer; { образец для поиска}
verh:integer; { верхняя граница поиска }
niz: integer; { нижняя граница поиска }
sred:integer; { номер среднего элемента )
found:boolean; { TRUE — совпадение образца с элементом массива }
n:integer; / число сравнений с образцом }
i:integer;
begin
// ввод массива и образца
for i:=l to SIZE do
a[i]:=StrToInt(StringGridl.Cells[i-l,0] ) ;
obr := StrToInt(Editl.text);
// поиск verh:=1;
niz:=SIZE; n:=0;
found:=FALSE; labels.caption:='';
if CheckBoxl.State = cbChecked
then Labels.caption: ='verh'+#9+'niz'#9'sred' #13;
// бинарный поиск в массиве repeat
sred:=Trunc ( (niz-verh) /2)+verh; if CheckBox1.Checked
then Labels.caption:=label3.caption +IntToStr(yerh) + #9
+IntToStr(niz) + #9 +IntToStr(sred) + #13; n:=n+1;
if a[sred] = obr then found:=TRUE else
if obr < a[sred] then niz:=sred-1 else verh:=sred+1; until (verh > niz) or found;
if found
then labels.caption:=label3.caption
+'Совпадение с элементом номер 'IntToStr(sred)+#13 + ‘Сравнений ‘
IntToStr(n)
else label3.caption:=label3.caption
+'Образец в массиве не найден.';
// нажатие клавиши в ячейке StringGrid
procedure TForml.StringGridlKeyPress(Sender: TObject; var Key: Char),
if Key = #13 then // нажата клавиша
if StringGrid1.Col < StringGridl.ColCount - 1 then // курсор в следующую ячейку таблицы StringGridl.Col := StringGrid1.Col +1 else // курсор в поле Editl, в поле ввода образца Editl.SetFocus; // нажатие клавиши в поле Editl procedure TForm1.Edit1KeyPress(Sender: TObject;. var Key: Char); if Key = #13 // нажата клавиша
then // сделать активной командную кнопку
Button1.SetFocus;
end.Ниже приведены примеры диалоговых окон программы Бинарный поиск в массиве после выполнения поиска— с выводом протокола (рис. 5.14, а) и без протокола (рис. 5.14, б).
Здесь следует обратить внимание на то, что элемент массива, находящийся на седьмом месте, программа бинарного поиска находит всего за четыре шага, в то время как программе, реализующей алгоритм простого перебора, потребовалось бы семь шагов.