Бинарный поиск в массивеDelphi , Синтаксис , МассивыБинарный поиск в массивеНа практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде — по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод бинарного поиска. Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец). Метод (алгоритм) бинарного поиска реализуется следующим образом: 1. Сначала образец сравнивается со средним (по номеру) элементом массива
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. Комментарии и вопросыМатериалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.
|
||||
©KANSoftWare (разработка программного обеспечения, создание программ, создание интерактивных сайтов), 2007 |