Метод бинарного поиска
В листинге 5.8 приведен текст процедуры обработки события Onclick для командной кнопки Поиск (Button1). Процедура вводит значения элементов массива и образец, затем, используя алгоритм бинарного поиска, проверяет, содержит ли массив элемент, равный образцу. Кроме того, переменная п (число сравнений с образцом) позволяет оценить эффективность алгоритма бинарного поиска по сравнению с поиском методом простого перебора.
При вычислении номера среднего элемента используется функция тгипс, которая округляет до ближайшего целого и преобразует к типу integer выражение, полученное в качестве аргумента. Необходимость использования тгипс объясняется тем, что выражение (niz-verh) /2 – дробного типа, переменная sred – целого, а переменной целого типа присвоить дробное значение нельзя (компилятор выдаст сообщение об ошибке).
Обратите внимание на процедуры обработки события onKeyPress для компонентов stringGrid1 и Edit1. Первая из них обеспечивает перемещение курсора в следующую ячейку таблицы или в поле Edit1 (из последней ячейки) в результате нажатия клавиши Enter, вторая – активизирует командную кнопку Поиск также в результате нажатия клавиши Enter.
Листинг 5.8. Бинарный поиск в массиве.
unit b_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 StringGrid1KeyPress(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: = 1 to SIZE do
a[i]: = StrToInt(StringGrid1.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
+'Образец в массиве не найден.';
end;
// нажатие клавиши в ячейке StringGrid
procedure TForml.StringGrid1KeyPress(Sender: TObject; var Key: Char),
begin
if Key = #13 then // нажата клавиша Enter
if StringGrid1.Col < StringGrid1.ColCount -1
then // курсор в следующую ячейку таблицы
StringGrid1.Col: = StringGrid1.Col +1
else // курсор в поле Editl, в поле ввода образца
Editl.SetFocus;
end;
// нажатие клавиши в поле Editl
procedure TForm1.Edit1KeyPress(Sender: TObject; .var Key: Char);
begin
if Key = #13 // нажата клавиша Enter
then // сделать активной командную кнопку
Button1.SetFocus;
end;
end.