Бинарный поиск в массиве

Delphi , Синтаксис , Массивы

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

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

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

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

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

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

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
  // нажата клавиша <Enter>
  if Key = #13 then // сделать активной командную кнопку
    Button1.SetFocus;
end;

end.

Статья Бинарный поиск в массиве раздела Синтаксис Массивы может быть полезна для разработчиков на Delphi и FreePascal.

Комментарии и вопросы

:: Главная :: Массивы ::