Різниця між бінарним пошуком та лінійним пошуком

Двійковий пошук проти лінійного пошуку

Лінійний пошук, також відомий як послідовний пошук, є найпростішим алгоритмом пошуку. Він шукає вказане значення у списку, перевіряючи кожен елемент у списку. Бінарний пошук - це також метод, який використовується для пошуку визначеного значення у відсортованому списку. Бінарний спосіб пошуку вдвічі зменшує кількість перевірених елементів (у кожній ітерації), скорочуючи час, необхідний для пошуку даного елемента у списку.

Що таке лінійний пошук?

Лінійний пошук - це найпростіший спосіб пошуку, який перевіряє кожен елемент у списку послідовно, поки не знайде заданий елемент. Вхід до методу лінійного пошуку - це послідовність (наприклад, масив, колекція або рядок) та елемент, який потрібно шукати. Вихід є істинним, якщо зазначений елемент знаходиться в межах заданої послідовності, або помилковим, якщо він не знаходиться в послідовності. Оскільки цей метод перевіряє кожен елемент у списку, поки не знайдеться зазначений елемент, у гіршому випадку він пройде через усі елементи у списку, перш ніж знайде потрібний елемент. Складність лінійного пошуку становить o (n). Тому вважається занадто повільним, щоб використовувати його при пошуку елементів у великих списках. Але це дуже просто і простіше у виконанні.

Що таке двійковий пошук?

Двійковий пошук - це також метод, який використовується для пошуку певного елемента в відсортованому списку. Цей метод починається з порівняння шуканого елемента з елементами в середині списку. Якщо порівняння визначає, що два елементи рівні, метод зупиняється і повертає положення елемента. Якщо шуканий елемент перевищує середній елемент, він знову запускає метод, використовуючи лише нижню половину відсортованого списку. Якщо шуканий елемент менше середнього елемента, він знову запускає метод, використовуючи лише верхню половину відсортованого списку. Якщо шуканий елемент не знаходиться в списку, метод поверне унікальне значення, що вказує на це. Тому метод бінарного пошуку вдвічі зменшує кількість елементів, що порівнюються (у кожній ітерації), залежно від результату порівняння. Отже, двійковий пошук працює в логарифмічний час, що призводить до середньої продуктивності випадку (log n).

Яка різниця між бінарним пошуком та лінійним пошуком?

Незважаючи на те, що і лінійний пошук, і двійковий пошук є методами пошуку, вони мають кілька відмінностей. У той час як двійковий пошук працює за відсортованими списками, пошук ліній може також працювати і в несортивних списках. Сортування списку зазвичай має середню складність випадку n log n. лінійний пошук простий і простіший у здійсненні, ніж двійковий пошук. Але лінійний пошук занадто повільний, щоб використовувати його у великих списках через його (n) середньої продуктивності. З іншого боку, двійковий пошук вважається більш ефективним методом, який можна використовувати у великих списках. Але реалізація двійкового пошуку може бути досить складною, і дослідження показало, що точний код двійкового пошуку можна знайти лише у п'яти з двадцяти книг.