Метод бінарного пошуку

На практиці досить часто проводиться пошук в масиві, елементи якого впорядковані по деякому критерієм (такі масиви називаються впорядкованими). Наприклад, масив прізвищ, як правило, впорядкований за алфавітом, масив даних про погоду – по датах спостережень. У разі, якщо масив впорядкований, то застосовують інші, більш ефективні по порівняно з методом простого перебору алгоритми, один з яких – метод бінарного пошуку.

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

Метод (алгоритм) бінарного пошуку реалізується в такий спосіб:

  1. спочатку зразок порівнюється із середнім (за номером) елементом масиву (рис. 5.10, а).
  • Якщо зразок дорівнює середньому елементу, то задача вирішена.
  • Якщо зразок більше середнього елемента, то це означає, що шуканий елемент розташований нижче середнього елемента (Між елементами з номерами sred + 1 і niz), і за нове значення verb приймається sred + i, а значення niz не змінюється (рис. 5.10, б).
  • Якщо зразок менше середнього елемента, то це означає, що шуканий елемент розташований вище середнього елемента (Між елементами з номерами verh і sred-1), і за нове значення niz приймається sred-1, а значення verh не змінюється (рис. 5.10, в).

a

б

в

Рис. 5.10. Вибір середнього елемента масиву при бінарному пошуку

Рис. 5.11. Алгоритм бінарного пошуку в упорядкованому за зростанням масиві

  1. Після того як визначена частина масиву, в якій може перебувати шуканий елемент, за формулою (niz-verh) / 2 + verh обчислюється нове значення sred і пошук триває.

Алгоритм бінарного пошуку, блок-схема якого представлена на рис. 5.11, закінчує свою роботу, якщо шуканий елемент знайдений або якщо перед виконанням чергового циклу пошуку виявляється, що значення verh більше, ніж niz.
Вид діалогового вікна програми Бінарний пошук в масиві наведено на рис. 5.12. поле мітки Label3 використовується для виведення результатів пошуку і протоколу пошуку. протокол пошуку виводиться, якщо встановлений прапорець виводити протокол. Протокол містить значення змінних verh, niz, sred. Ця інформація, що виводиться під час пошуку, корисна для розуміння суті алгоритму.

Рис. 5.12. Діалогове вікно програми Бінарний пошук в масиві

В формою додатка з’явився новий компонент, який до цього моменту в програмах не використовувався, – прапорець (компонент CheckBox). Значок компонента checkBox знаходиться на вкладці Standard (рис. 5.13). Додається до форми він точно так само, як і інші компоненти. Властивості компонента CheckBox перераховані в табл. 5.5.

Таблиця 5.5. Властивості компонента CheckBox

Властивість Визначає
Name Ім’я компонента. використовується в програмі для доступу до властивостей компонента
Caption Текст, що пояснює призначення прапорця
Checked Стан, зовнішній вигляд прапорця: якщо прапорець встановлений (в квадратику є & quot; галочка & quot;), то checked = TRUE; якщо прапорець скинутий (немає & quot; галочки & quot;), то Checked = FALSE
State Стан прапорця. На відміну від властивості Checked, дозволяє розрізняти встановлене, скинуте і проміжне стану. Стан прапорця визначають константи:
cbChecked (встановлений); cbGrayed (сірий, невизначений стан); cbUnChecked (скинутий)
AllowGrayed Чи може прапорець бути в проміжному стані: якщо AllowGrayed = FALSE, то прапорець може бути тільки встановленим або скинутим;
якщо AllowGrayed = TRUE, то допустимо проміжний стан
Left Відстань від лівої межі прапорця до лівої межі форми
Top Відстань від верхньої межі прапорця до верхньої межі форми
Height  

Висоту поля виведення поясняющего тексту
Width Ширину поля виведення поясняющего тексту
Font  

Шрифт, використовуваний для відображення поясняющего тексту
ParentFont Ознака спадкоємства характеристик шрифту батьківської форми

Рис. 5.13. Компонент CheckBox

Після того як компонент CheckBox буде додано до форми, а додається він звичайним чином, потрібно встановити значення його властивостей відповідно до табл. 5.6.

Таблиця 5.6. Значення властивостей компонента CheckBox1

Властивість Значення
Caption Виводити протокол
Checked True

У лістингу 5.8 приведений текст процедури обробки події Onclick для командної кнопки Пошук (Button1). Процедура вводить значення елементів масиву і зразок, потім, використовуючи алгоритм бінарного пошуку, перевіряє, чи містить масив елемент, рівний зразком. Крім того, змінна п (число порівнянь із зразком) дозволяє оцінити ефективність алгоритму бінарного пошуку в порівнянні з пошуком методом простого перебору.

При обчисленні номера середнього елемента використовується функція тгіпс, яка округлює до найближчого цілого і перетворює до типу integer вираз, отримане в якості аргументу. Необхідність використання тгіпс пояснюється тим, що вираз (niz-verh) / 2 – дрібного типу, змінна sred – цілого, а змінної цілого типу привласнити дробове значення не можна (компілятор видасть повідомлення про помилку).

Зверніть увагу на процедури обробки події onKeyPress для компонентів stringGridl і Editl. Перша з них забезпечує переміщення курсору в наступний елемент таблиці або в поле Editl (з останньої клітинки) в результаті натискання клавіші ” Enter”, друга – активізує командну кнопку Пошук також в результаті натискання клавіші “Enter”.

Лістинг 5.8. Бінарний пошук в масиві

unit b_found_;
interface
uses
Windows, Messages, SysUtils, Classes,

Graphics, Cont rols, 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, б).

Тут слід звернути увагу на те, що елемент масиву, що знаходиться на сьомому місці, програма бінарного пошуку знаходить все за чотири кроки, в той час як програму, що реалізує алгоритм простого перебору, треба було б сім кроків.

а

б

Рис. 5.14. Приклади роботи програми бінарного пошуку в масиві

 

Post Views: 3 358
➤