Void main()

{ unsigned N; // кількість елементів у вихідному масиві

int sample; // зразок для пошуку

int k = -1; // результат пошуку :

// k = -1, якщо елемент не знайдений,

// якщо k >= 0, то k – номер першого елемента в масиві, // співпадаючого зі зразком

printf("Розмір масиву N = "); scanf("%u",&N);

int* A = new int[N]; // створення робочого масиву

printf("Введіть елементи масиву: \n");

for(k=0; k<N; k++) scanf("%d",&a[k]);

printf("Зразок для пошуку = "); scanf ("%d", &sample);

for (int i=0; i<N; i++)

// послідовний перегляд всіх елементів масиву

{ if (A[i]==sample) { k = i; break; }

}

if (k>=0) printf("Пошук успішний. Збіг з елементом %d.\n", k);

else printf("Зразок у масиві відсутній \n");

}

Протокол роботи програми:

Розмір масиву N = 6

Введіть елементи масиву:

4 67 8 14 78 9

Зразок для пошуку = 78

Пошук успішний. Збіг з елементом 5.

Алгоритм бінарного пошуку

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

Суть методу бінарного пошуку полягає в наступному. Будемо вважати, що масив впорядкований по зростанню. Позначимо як s зразок для пошуку.

1. Покласти bot = 0, top = N-1.

2. Обчислити m = bot+(top-bot)/2.

3. Якщо s == A[m] , то процес завершити.

4. Якщо s < A[m], то покласти top = m.

Якщо ні, то покласти bot = m.

Перейти до п. 2.

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

// Приклад 2

#include <syst.h>