Бинарный поиск в массиве
Листинг 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 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
+'Образец в массиве не найден.';
end;
// нажатие клавиши в ячейке StringGrid
procedure TForml.StringGridlKeyPress(Sender: TObject; var Key: Char),
begin
if Key = #13 then // нажата клавиша <Enter>
if StringGrid1.Col < StringGridl.ColCount - 1
then // курсор в следующую ячейку таблицы
StringGridl.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.
Ниже приведены примеры диалоговых окон программы Бинарный поиск в массиве после выполнения поиска— с выводом протокола (Рисунок 5.14, а) и без протокола (Рисунок 5.14, б).
Здесь следует обратить внимание на то, что элемент массива, находящийся на седьмом месте, программа бинарного поиска находит всего за четыре шага, в то время как программе, реализующей алгоритм простого перебора, потребовалось бы семь шагов.
