Индексно-послідовний пошук
Більш ефективний спосіб пошуку значення у відсортованому масиві. Але більш вимогливий до ресурсів.
Бінарний пошук
Бінарний (двійковий) пошук — це алгоритм знаходження елемента масиву послідовним діленням масиву навпіл і сравниванием вихідного числа з числом з середини масиву. Якщо число з середини менше шуканого, шукаємо далі, у другій частині, якщо більше — продовжуємо пошук в першій. Алгоритм найшвидший з усіх перерахованих і працює наступним чином:
- Спочатку дізнаємося значення об’єкта в середині масиву. Перевіряємо на відповідність з вихідним значенням.
- Якщо значення з середини менше вихідного, то продовжуємо пошук у другій половині, якщо більше — шукаємо в першій.
- В отриманій половині поступаємо таким же чином: ділимо її на половину і порівнюємо отримане значення.
Пошук відбувається до моменту, поки початкове значення не стане дорівнює значенню в масиві. Якщо такого не відбувається — значить даного значення в масиві немає.
Є декілька підводних каменів, які можуть зустрітися при проектуванні двійкового пошуку.
