Бінарний пошук

Бінарний пошук

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

Алгоритм

1.Вибрати середній елемент A[c] і порівняти з  X.

2.Якщо X = A[c], знайшли (вихід).

3.Якщо X < A[c], шукати дальше в першій половині.

4.Якщо X > A[c], шукати дальше в другій половині.

Практичне завдання

1. Дано масив цілих чисел: 0, 6, 8, 13, 17, 19, 30, 55, 78, 103, 211, 345, 451, 562, 679, 783, 800. Розробіть програму визначення позиції, на якій знаходиться число, значення якого вводиться з клавіатури.

2. Створіть масив з 50 випадкових чисел у діапазоні від -100 до 100. Здійснити наявність числа, введеного користувачем з клавіатури у даному масиві. Вивести на екран відповідь чи наявне число та згенерований масив.