Бинарный поиск

== Бинарный поиск в целочисленном массиве ==
{ **** UBPFD *********** by kladovka.net.ru ****
>> Бинарный поиск
Бинарный поиск в целочисленном массиве - шаблон для функции,
выполняющей бинарный поиск.
X - значение, которое ищется
A - массив в котором происходит поиск.
возвращаемое значение
индекс элемента, начиная с которого значения в массиве превышают заданное значение
в случае точного поиска заменить строку Result := L и -1 будет свидетельствовать
о том, что значение не найдено.
Зависимости: System
Автор: Mystic, mystic2000@newmail.ru, ICQ:125905046, Харьков
Copyright: Mystic
Дата: 25 апреля 2002 г.
********************************************** }
function BinaryFind(X: Integer; A: array of Integer): Integer;
 function RecurceFind(L,R: Integer): Integer;
 var
 M: Integer;
 begin
 if R < L then
 begin
 Result := L; // Result := -1 если поиск точный
 Exit;
 end;
 M := (L+R) div 2;
 if A[M] = X then
 begin
 Result := M;
 Exit;
 end;
 if A[M] > X then
 Result := RecurceFind(L, M-1)
 else
 Result := RecurceFind(M+1, R)
 end;
begin
 Result := RecurceFind(Low(A), High(A));
end;
Author: Mystic
ID: 04191
----
== Усовершенствование бинарного поиска ==
Примечания: Александр Шарахов
Функцию BinaryFind можно усовершенствовать по нескольким направлениям:
# Повысить скорость работы, избавившись от рекурсии.
# При положительном результате поиска всегда возвращать индекс первого подходящего элемента.
# Совместить в одном флаконе точный и неточный поиск. Для этого при отрицательном результате поиска возвращать отрицательное значение Index-MaxInt, где Index - индекс первого элемента массива, больше искомого. Если такой элемент отсутствует, то возвращать (High(a)+1)-MaxInt.
Вот что у меня получилось:
function BinaryFind2(x: Integer; const a: array of Integer): Integer;
var
 i, j, m: Integer;
 found: Boolean;
begin;
 found := False;
 i := -1;
 j := High(a);
 while True do
 begin
 if i >= j then break;
 m := (i+j+1) shr 1;
 if a[m] < x then
 i := m
 else
 begin
 j := m-1;
 if a[m] = x then
 found := True;
 end;
 end;
 Result := i+1;
 if not found then
 Dec(Result, MaxInt);
end;
Константиныч
Точно не проверял, но походу работает только если каждый элемент массива уникален. В противном случае будет выдаваться не первый элемент, подходящий по критерию поиска.
И надо было упомянуть, что массив должен быть отсортирован по возрастанию.
ID: 04192
----
== Бинарный поиск в массиве ==
На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде - по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых - метод бинарного поиска.
Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).
Метод (алгоритм) бинарного поиска реализуется следующим образом:
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.
Source: http://delphiworld.narod.ru/
ID: 04193
----
Category:Алгоритмы