Розділ 1. Теоритична частина. 
Пошук та сортування одновимірних масивів

Пошук елемента в одновимірному масиві

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

тип = масив [1.n] із t;

змін a: ;

де для типу елементів масиву t визначені стандартні відношення: {=,, , >=, <=}.

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

Виникає питання: чи можна знайти у масиві потрібний елемент за меншу кількість кроків? Відповідь є ствердною в тому випадку, коли елементи масиву впорядковані. Без обмеження загальності можна вважати, що елементи впорядковані за зростанням, тобто a[1] <= a[2] <= … <= a[n]. Ідея методу пошуку, який називають бінарним, полягає у наступному:

На кожному кроці алгоритму шукаємо x серед елементів масиву від нижньої до верхньої границі. Спочатку нижня границя індексів — 1, а верхня — n.

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

Ось приклад функції, яка здійснює такий пошук.

int binary_search (int a[], int low, int high, int target) {.

while (low <= high) {.

int middle = low + (high — low)/2;

if (target < a[middle]).

high = middle — 1;

else if (target > a[middle]).

low = middle + 1;

else.

return middle;

}.

return -1;}.