Зміст:
Визначення - Що означає Бінарний пошук?
Бінарний алгоритм пошуку використовується для пошуку позиції конкретного значення, що міститься в відсортованому масиві. Працюючи з принципом ділення і підкорення, цей алгоритм пошуку може бути досить швидким, але застереження полягає в тому, що дані повинні бути у відсортованій формі. Це працює, починаючи пошук в середині масиву і працюючи вниз по першій нижній або верхній половині послідовності. Якщо середнє значення нижче цільового значення, це означає, що пошук повинен піднятися вище, якщо ні, то він повинен шукати на низхідній частині масиву.
Двійковий пошук також відомий як пів-інтервальний пошук або логарифмічний пошук.
Техопедія пояснює Бінарний пошук
Двійковий пошук - це швидкий та ефективний метод пошуку конкретного цільового значення з набору впорядкованих елементів. Почавши в середині відсортованого списку, він може ефективно скоротити простір пошуку навпіл, визначивши, чи підніматись чи опускати список, виходячи з медіанного значення порівняно з цільовим значенням.
Наприклад, із цільовим значенням 8 та пошуковим простором від 1 до 11:
- Знайдено медіану / середнє значення і на ньому встановлено покажчик, який у цьому випадку дорівнює 6.
- Ціль 8 порівнюється з 6. Оскільки 6 менше, ніж 8, ціль має бути у вищій половині.
- Вказівник переміщується на наступне значення (7) і порівнюється з цільовим. Він менший, тому вказівник переходить на наступне вище значення.
- Покажчик зараз на 8. Порівнюючи це з цільовим, це точна відповідність, тому ціль знайдена.
Використовуючи двійковий пошук, ціль потрібно було лише порівняти з трьома значеннями. У порівнянні з лінійним пошуком, він би починався з самого першого значення і переміщувався вгору, потребуючи порівняння цілі до восьми значень. Двійковий пошук можливий лише з упорядкованим набором даних; якщо дані розташовані випадковим чином, то лінійний пошук давав би результати весь час, тоді як двійковий пошук, ймовірно, застряг у нескінченному циклі.
