а рекурсії, його дуже легко реалізувати як нерекурсивний алгоритм. Ось псевдокод нерекурсивною версії
АЛГОРИТМ Binary Search (А [0 .. п - 1], К)
// Реалізує нерекурсивний бінарний пошук
// Вхідні дані: Масив А [0 .. п - 1], відсортований
// у зростаючому порядку, і шуканий ключ К
// Вихідні дані: Індекс елемента масиву, рівного К,
// або -1, якщо такого елемента немає
l = 0;
r = n - 1
while l r do
т =; К = А [т] mif К <А [т] = m - 1
r = m + 1
return -1
Стандартний спосіб аналізу ефективності бінарного пошуку полягає в підрахунку кількості порівнянь шуканого ключа з елементами масиву. Крім того, з міркувань простоти, ми будемо вважати, що використовуються потрійні порівняння, тобто що одне порівняння К і А [m] дозволяє визначити, чи менше К, більше або дорівнює значенню А [m].
Скільки ж порівнянь повинен виконати алгоритм при пошуку в масиві з n елементів? Відповідь, очевидно, залежить не тільки від n, але і від конкретного екземпляра задачі. Знайдемо кількість порівнянь у найгіршому випадку. У найгірший випадок входять всі масиви, які не містять шуканого ключа (крім них в цей розряд потрапляють і деякі масиви, пошук у яких завершується успішно). p> Зокрема, буде потрібно не більше ніж 10 потрійних порівнянь для пошуку елемента із заданим значенням (або з'ясування того, що такий елемент відсутній) в масиві з 1000 елементів, і не більше 20 порівнянь для пошуку в масиві в мільйон елементів.
Пошук підрядка:
Опис завдання пошуку підрядка: дана символьний рядок довжиною п, що називається текстом, і рядок довжиною т (т п). іменована шаблоном (pattern); потрібно знайти в тексті підрядок, відповідну шаблоном. Говорячи точніше, потрібно визначити i - індекс крайнього зліва символу першої відповідної шаблоном підрядка в тексті. p align="justify"> Якщо потрібно знайти всі такі підрядка, алгоритм пошуку підрядка може просто продовжувати роботу до повної перевірки тексту.
Алгоритм, заснований на грубій силі, очевидний: шаблон вирівнюється з початком тексту і по черзі порівнюються відповідні пари символів зліва направо до тих пір або символи у всіх т парах будуть рівні (у цьому випадку алгоритм може припиняти роботу ), або не зустрічається пара різних символів. В останньому випадку шаблон зміщується на одну позицію вправо, і порівняння символів триває, починаючи з першого символу шаблону і символу у відповідній позиції в тексті. Зауважимо, що остання позиція у тексті, яка ще може виступати в ролі початку шуканої підрядка - п - т (якщо позиції в тексті індексуються значеннями від 0 до п - 1). Після цієї позиції в тексті залишається занадто мало символів, щоб вони могли відповідати шаблоном. Отже, після досягнення зазначеної позиції алгоритм н...
