Перш ніж розуміти відмінності між лінійним і двійковим пошуком, ми повинні спочатку знати лінійний пошук і двійковий пошук окремо.
Що таке лінійний пошук?
Лінійний пошук також відомий як послідовний пошук, який просто сканує кожен елемент за раз. Припустімо, ми хочемо шукати елемент у масиві чи списку; ми просто обчислюємо його довжину і не стрибаємо ні на один предмет.
Розглянемо простий приклад.
Припустимо, у нас є масив із 10 елементів, як показано на малюнку нижче:
На малюнку вище показано масив символьного типу з 10 значеннями. Якщо ми хочемо шукати «E», тоді пошук починається з 0тиселемент і сканує кожен елемент, доки елемент, тобто «E», не буде знайдено. Ми не можемо безпосередньо перейти від 0тиселемент до 4тиселемент, тобто кожен елемент сканується один за одним, поки елемент не буде знайдено.
Складність лінійного пошуку
Лінійний пошук сканує кожен елемент один за одним, поки елемент не буде знайдено. Якщо кількість елементів збільшується, кількість елементів для сканування також збільшується. Можна сказати, що час, витрачений на пошук елементів, пропорційний кількості елементів . Тому складність у найгіршому випадку дорівнює O(n)
Що таке бінарний пошук?
Бінарний пошук — це пошук, у якому обчислюється середній елемент, щоб перевірити, чи є він меншим або більшим за елемент, який потрібно шукати. Основна перевага використання бінарного пошуку полягає в тому, що він не сканує кожен елемент у списку. Замість сканування кожного елемента він виконує пошук до половини списку. Отже, двійковий пошук потребує менше часу для пошуку елемента порівняно з лінійним пошуком.
Один передумова двійкового пошуку полягає в тому, що масив має бути у відсортованому порядку, тоді як лінійний пошук працює як з відсортованим, так і з несортованим масивом. Алгоритм бінарного пошуку базується на техніці «розділяй і володарюй», що означає рекурсивний розподіл масиву.
У двійковому пошуку використовуються три випадки:
Випадок 1: дані
Випадок 2: data>a[mid] then right=mid-1
Випадок 3: дані = a[mid] // знайдено елемент
У наведеному вище випадку ' a ' - ім'я масиву, середина індекс елемента, обчислений рекурсивно, даних це елемент, який потрібно шукати, зліва позначає лівий елемент масиву і правильно позначає елемент, який знаходиться в правій частині масиву.
Давайте зрозуміємо роботу бінарного пошуку на прикладі.
Припустимо, що у нас є масив розміром 10, який має індекс від 0 до 9, як показано на малюнку нижче:
Ми хочемо знайти 70 елементів із наведеного вище масиву.
Крок 1: Спочатку ми обчислюємо середній елемент масиву. Ми розглядаємо дві змінні, тобто ліву та праву. Спочатку ліворуч =0 і праворуч=9, як показано на малюнку нижче:
Значення середнього елемента можна розрахувати як:
Отже, mid = 4 і a[mid] = 50. Елемент, який потрібно шукати, становить 70, тому a[mid] не дорівнює даним. Випадок 2 задовольняється, тобто data>a[mid].
крок 2: Оскільки data>a[mid], значення left збільшується на mid+1, тобто left=mid+1. Значення mid дорівнює 4, тому значення left стає 5. Тепер у нас є підмасив, як показано на малюнку нижче:
Тепер знову середнє значення обчислюється за допомогою наведеної вище формули, і значення mid стає 7. Тепер середнє значення можна представити як:
На наведеному вище малюнку ми бачимо, що a[mid]>data, тому значення mid буде обчислено на наступному кроці.
крок 3: Як [mid]>data, значення права зменшується на mid-1. Значення mid дорівнює 7, тому значення right стає 6. Масив можна представити так:
Значення середини буде обчислено знову. Значення лівого і правого 5 і 6 відповідно. Таким чином, значення mid дорівнює 5. Тепер mid можна представити в масиві, як показано нижче:
На наведеному вище малюнку ми можемо спостерігати, що [серед]
крок 4: Як [середина] Тепер значення mid знову обчислюється за формулою, яку ми вже обговорювали. Значення лівого та правого дорівнюють 6 і 6 відповідно, тому значення середини стає 6, як показано на малюнку нижче: Ми можемо помітити на малюнку вище, що a[mid]=data. Таким чином, пошук завершено, і елемент знайдено успішно. Нижче наведено відмінності між лінійним пошуком і бінарним пошуком: опис Лінійний пошук — це пошук, який знаходить елемент у списку шляхом послідовного пошуку елемента, поки елемент не буде знайдено в списку. З іншого боку, двійковий пошук — це пошук, який знаходить середній елемент у списку рекурсивно, доки середній елемент не буде зіставлений із шуканим елементом. Робота обох пошуків Лінійний пошук починає пошук з першого елемента та сканує один елемент за раз без переходу до наступного елемента. З іншого боку, бінарний пошук ділить масив навпіл шляхом обчислення середнього елемента масиву. Реалізація Лінійний пошук може бути реалізований на будь-якій лінійній структурі даних, такій як вектор, однозв’язаний список, подвійний зв’язаний список. Навпаки, бінарний пошук може бути реалізований на тих структурах даних з двостороннім обходом, тобто обходом вперед і назад. Складність Лінійний пошук простий у використанні або, можна сказати, менш складний, оскільки елементи для лінійного пошуку можна розташовувати в будь-якому порядку, тоді як у бінарному пошуку елементи мають бути розташовані в певному порядку. Відсортовані елементи Елементи для лінійного пошуку можна розташувати у довільному порядку. У лінійному пошуку не обов’язково, щоб елементи розташовувалися в порядку сортування. З іншого боку, у бінарному пошуку елементи мають бути впорядковані. Його можна розташувати як за зростанням, так і за спаданням, відповідно змінюватиметься алгоритм. Оскільки бінарний пошук використовує відсортований масив, необхідно вставити елемент у належне місце. Навпаки, для лінійного пошуку не потрібен відсортований масив, тому новий елемент можна легко вставити в кінець масиву. Підхід Лінійний пошук використовує ітераційний підхід для пошуку елемента, тому він також відомий як послідовний підхід. Навпаки, бінарний пошук обчислює середній елемент масиву, тому він використовує підхід розділяй і володарюй. Набір даних Лінійний пошук не підходить для великого набору даних. Якщо ми хочемо шукати елемент, який є останнім елементом масиву, лінійний пошук розпочне пошук з першого елемента й триватиме до останнього елемента, тому час, витрачений на пошук елемента, буде великим. З іншого боку, двійковий пошук підходить для великого набору даних, оскільки займає менше часу. швидкість Якщо в лінійному пошуку набір даних великий, обчислювальна вартість буде високою, а швидкість стає низькою. Якщо набір даних великий у двійковому пошуку, тоді витрати на обчислення будуть меншими порівняно з лінійним пошуком, а швидкість стає високою. Розміри Лінійний пошук можна використовувати як для одновимірного, так і для багатовимірного масиву, тоді як бінарний пошук можна реалізувати лише для одновимірного масиву. Ефективність Лінійний пошук менш ефективний, коли ми розглядаємо великі набори даних. Двійковий пошук є більш ефективним, ніж лінійний пошук у випадку великих наборів даних. Розглянемо відмінності в табличній формі. 
Відмінності між лінійним пошуком і бінарним пошуком
масив байтів у рядок
Основа порівняння Лінійний пошук Двійковий пошук Визначення Лінійний пошук починається з першого елемента та порівнює кожен елемент із шуканим елементом, доки цей елемент не буде знайдено. Він знаходить позицію шуканого елемента шляхом знаходження середнього елемента масиву. Відсортовані дані У лінійному пошуку елементи не потрібно впорядковувати в порядку сортування. Передумовою для бінарного пошуку є те, що елементи мають бути впорядковані. Реалізація Лінійний пошук можна реалізувати на будь-якій лінійній структурі даних, такій як масив, зв’язаний список тощо. Реалізація бінарного пошуку обмежена, оскільки він може бути реалізований лише на тих структурах даних, які мають двосторонній обхід. Підхід Він заснований на послідовному підході. Він базується на підході «розділяй і володарюй». Розмір Переважно для невеликих наборів даних. Переважно для масивів даних великого розміру. Ефективність Він менш ефективний у випадку великих наборів даних. Це більш ефективно у випадку великих наборів даних. Найгірший випадок У лінійному пошуку найгіршим сценарієм для пошуку елемента є O(n). У бінарному пошуку найгіршим сценарієм для пошуку елемента є O(log2n). Найкращий сценарій У лінійному пошуку найкращим сценарієм для пошуку першого елемента в списку є O(1). У бінарному пошуку найкращим сценарієм для пошуку першого елемента в списку є O(1). Розмірний масив Його можна реалізувати як на одновимірному, так і на багатовимірному масиві. Його можна реалізувати тільки на багатовимірному масиві.