Двійковий (бінарний) пошук

Коли пошук деякого елемента необхідно здійснити в впорядкованої за зростанням або спаданням послідовності, тоді пріменѝм алгоритм двійкового (бінарного) пошуку. Метод використовує стратегію «розділяй і володарюй», а саме: задана послідовність ділиться на дві рівні частини і пошук здійснюється в одній з цих частин, яка потім також ділиться надвоє, і так до тих пір, поки виявиться наявність шуканого елемента або його відсутність. Використовувати цю операцію, зменшуючи кожен раз зону пошуку вдвічі, дозволено лише виходячи з того факту, що елементи послідовності заздалегідь впорядковані. Знайшовши середній елемент (зробити це, знаючи число елементів масиву, не важко), і порівнявши його значення з шуканим, можна впевнено сказати, де відносно середнього елемента знаходиться шуканий елемент.

Далі, будемо вважати, що елементи масиву розташовуються в порядку зростання, оскільки немає істотної різниці, як саме вони впорядковані: за зростанням або спаданням значення. Також позначимо межі зони пошуку через left і right - крайній лівий і крайній правий елементи відповідно.

Хід роботи алгоритму, розділений на етапи, виглядає наступним чином:

  1. зона пошуку (на першому кроці їй є весь масив) ділитися на дві рівні частини, шляхом визначення її середнього (mid) елемента;
  2. середній елемент порівнюється з шуканим (key), результатом цього порівняння буде один з трьох випадків:
      • key
      • key> mid. Крайній лівій кордоном області пошуку стає наступний за середнім елемент (left ← mid + 1);
      • key = mid. Значення середнього і шуканого елементів збігаються, отже елемент знайдений, робота алгоритму завершується.
  3. якщо для перевірки не залишилося жодного елемента, то алгоритм завершується, інакше виконується перехід до пункту 1.

У таблиці нижче представлений конкретний цілочисельний масив, і послідовне виконання алгоритму бінарного пошуку стосовно його елементів. Для економії місця в таблиці left, right і mid замінені на a, b і c.

Двійковий (бінарний) пошук

Є послідовність цілих чисел, розташованих в порядку зростання, а також ключ - число 16. Спочатку граничними елементами є елементи з номерами 1 і 9, і значеннями 1 і 81. Обчислюється номер середнього елемента, для чого, як правило, використовується формула (right + left) / 2, або left + (right-left) / 2 (далі, в програмах буде використана друга формула, як найбільш стійка до переповненого). Після порівняння виявляється, що шуканий елемент менше середнього, і тому подальший пошук здійснюється в лівій частині послідовності. Алгоритм залишиться активним подібним чином, до знаходження на 4 кроці шуканого елемента.

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

Код програми на C ++:

#include "stdafx.h"
#include
using namespace std;
const int N = 10;
// двійковий пошук
int BinarySearch # 40; int A # 91; # 93 ;. int key # 41;
# 123;
int left = 0. right = N, mid;
while # 40; left <= right )
# 123;
mid = left + # 40; right - left # 41; / 2;
if # 40; key else if # 40; key> A # 91; mid # 93; # 41; left = mid + 1;
else return mid;
# 125;
return - 1;
# 125;
// головна функція
void main # 40; # 41;
# 123;
setlocale # 40; LC_ALL, "Rus" # 41; ;
int i, key;
int A # 91; N # 93; ;
cout <<"Искомый элемент> "; Cin >> key; // введення ключа
cout <<"Исходный массив: " ;
for # 40; i = 0; i # 123; A # 91; i # 93; = N * i; cout <
if # 40; BinarySearch # 40; A, key # 41; == - 1 # 41; cout <<" \n Элемент не найден" ;
else cout <<" \n Номер элемента: " < system # 40; "Pause >> void" # 41; ;
# 125;

Код програми на Pascal:

program BinSearch;
uses crt;
const N = 10;
type Arr = array # 91; 1. N # 93; of integer;
var mid. left. right. key. i. integer;
A. Arr;

function BinarySearch # 40; A. Arr; key. integer # 41 ;. integer;
begin
left: = 1; right: = N;
while left<= right do
begin
mid: = left + # 40; right - left # 41; div 2;
if # 40; key
else if # 40; key> A # 91; mid # 93; # 41; then left: = mid + 1
else begin BinarySearch: = mid; exit; end;
end;
BinarySearch: = - 1;
end;

begin
write # 40; 'Бажаємий елемент>' # 41; ; read # 40; key # 41; ;
write # 40; 'Вихідний масив: ' # 41; ;
for i: = 1 to N do
begin A # 91; i # 93; : = N * i; write # 40; A # 91; i # 93 ;. '' # 41; ; end;
writeln;
if # 40; BinarySearch # 40; A. key # 41; = - 1 # 41; then write # 40; 'Елемент не найден' # 41;
else write # 40; 'Номер елемента:'. BinarySearch # 40; A. key # 41; # 41; ;
end.

У програмі можна було б реалізувати перевірку масиву на наявність в ньому елементів, але так як він заповнюється, незалежно від користувача, строго певною кількістю константних значень, це робити необов'язково.

У разі, коли перше значення mid збігається з ключем, тоді вважається, що алгоритм виконався за свій кращий час O (1). В середньому і найгіршому випадку час роботи алгоритму становить O (logn), що значно швидше, ніж у лінійного пошуку, що вимагає лінійного часу.

Дивіться також:

Схожі статті