Алгоритм бінарного пошуку є алгоритм пошуку, який використовується у відсортованому масиві шляхом багаторазового ділення інтервалу пошуку навпіл. Ідея бінарного пошуку полягає у використанні інформації про те, що масив відсортовано, і зменшенні часової складності до O(log N). 4 вересня 2024 р.
В інформатиці двійковий пошук, також відомий як напівінтервальний пошук, логарифмічний пошук або двійкове розділення, алгоритм пошуку, який знаходить позицію цільового значення в межах відсортованого масиву. Двійковий пошук порівнює цільове значення із середнім елементом масиву.
Двійковий пошук — це ефективні алгоритми, засновані на концепції «розділяй і володарюй”, який покращує пошук шляхом рекурсивного ділення масиву навпіл, доки ви не знайдете елемент або список не буде звужено до однієї частини, яка не відповідає потрібному елементу.
Алгоритм бінарного пошуку
- Крок 1: встановіть початок = нижня_межа, кінець = верхня_межа, позиція = – 1.
- Крок 2: повторіть кроки 3 і 4, поки початок <=кінець.
- Крок 3: встановіть середину = (початок + кінець)/2 або початок+(кінець-початок)/2.
- Крок 4: якщо a[mid] = target.
- встановити позицію = середину.
- друк поз.
- перейдіть до кроку 6.
- інакше, якщо a[mid] > target.
Відповідь: Порядок алгоритму бінарного пошуку такий O(log n), де n — розмір масиву або списку, у якому здійснюється пошук. Це означає, що часова складність алгоритму зростає логарифмічно зі збільшенням розміру вхідних даних, що робить його дуже ефективним для пошуку великих наборів даних.
Двійковий пошук: як це працює:
- Почніть з масиву, відсортованого в порядку спадання.
- На кожному кроці: виберіть середній елемент масиву m і порівняйте його з e. Якщо значення елементів рівні, повертається індекс m. Якщо e більше за m, то e має бути в лівому підмасиві. …
- Повторіть ці кроки для нового підмасиву.