Зміст

• Порівняльна діаграма
• Визначення лінійного пошуку
• Визначення двійкового пошуку
• Висновок

Лінійний пошук і двійковий пошук - це два методи, які використовуються в масивах пошук елементи. Пошук - це процес пошуку елемента в списку елементів, що зберігаються в будь-якому порядку або випадковим чином.

Основна відмінність лінійного пошуку від бінарного пошуку полягає в тому, що бінарний пошук потребує менше часу для пошуку елемента з відсортованого списку елементів. Тож робиться висновок, що ефективність методу бінарного пошуку більша, ніж лінійного пошуку.

Ще одна відмінність між ними полягає в тому, що існує необхідна умова для двійкового пошуку, тобто елементи повинні бути відсортовано тоді як у лінійному пошуку немає такої передумови. Хоча обидва способи пошуку використовують різні методи, які обговорюються нижче.

1. Порівняльна діаграма
2. Визначення
3. Ключові відмінності
4. Висновок

Порівняльна діаграма

Основа для порівняння	Лінійний пошук	Двійковий пошук
Часова складність	O (N)	O (журнал 2 N)
Кращий час справи	Перший елемент O (1)	Центр Елемент О (1)
Необхідна умова для масиву	Не потрібно	Масив повинен бути відсортованим
Найгірший випадок для N кількості елементів	Не потрібно проводити порівняння	Можна зробити висновок лише після журналу2N порівнянь
Можна реалізувати на	Список масивів та пов'язаних з ними	Не може бути безпосередньо реалізовано у зв’язаному списку
Вставте операцію	Легко вставляється в кінці списку	Потрібна обробка, щоб вставити її в потрібне місце для підтримки відсортованого списку.
Тип алгоритму	Ітеративний характер	Розділяйся і підкорюй на природі
Корисність	Простий у використанні і не потребує жодних замовлених елементів.	Будь-який складний алгоритм та елементи повинні бути організовані в порядку.
Рядки кодексу	Менше	Більше

Визначення лінійного пошуку

При лінійному пошуку кожен елемент масиву отримується один за одним у логічному порядку і перевіряється, бажаний він елемент чи ні. Пошук буде невдалим, якщо всі елементи доступні, а потрібний елемент не знайдеться. У гіршому випадку, кількість середнього випадку, можливо, нам доведеться сканувати половину розміру масиву (n / 2).

Тому лінійний пошук можна визначити як техніку, яка послідовно обходить масив, щоб знайти даний елемент. Програма, наведена нижче, ілюструє пошук елемента масиву за допомогою пошуку.

Ефективність лінійного пошуку

Витрата часу або кількість порівнянь, здійснених на пошук запису в таблиці пошуку, визначають ефективність методики. Якщо потрібний запис присутній у першому положенні таблиці пошуку, робиться лише одне порівняння. Коли потрібний запис є останнім, тоді необхідно зробити n порівнянь. Якщо запис повинен бути представлений десь у пошуковій таблиці, в середньому кількість порівнянь буде (n + 1/2). Найгірший показник ефективності цієї методики - O (n) означає порядок виконання.

Програма C пошук елемента за допомогою лінійної техніки пошуку.

#включати #включати void main () {int a, n, i, item, loc = -1; clrscr (); f (" nВведіть кількість елемента:"); scanf ("% d", & n); f ("Введіть числа: n"); для (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nВведіть номер для пошуку:"); scanf ("% d", & елемент); for (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; перерва; }} if (loc> = 0) {f (" n% d знайдено у позиції% d:", item, loc + 1); } else {f (" n Елемент не існує"); } getch (); }

Визначення двійкового пошуку

Двійковий пошук - надзвичайно ефективний алгоритм. Ця методика пошуку забирає менше часу на пошук даного товару за мінімально можливих порівнянь. Щоб виконати двійковий пошук, спочатку ми повинні сортувати елементи масиву.

Логіка цієї методики наведена нижче:

• Спочатку знайдіть середній елемент масиву.
• Середній елемент масиву порівнюється з елементом, який потрібно шукати.

Можуть виникнути три випадки:

1. Якщо елемент є необхідним елементом, то пошук успішний.
2. Коли елемент менше потрібного елемента, тоді шукайте лише першу половину масиву.
3. Якщо він більший за потрібний елемент, то шукайте у другій половині масиву.

Повторюйте ті ж дії, поки елемент не буде знайдений або вичерпаний в області пошуку. У цьому алгоритмі кожен раз область пошуку зменшується. Тому кількість порівнянь становить не більше журналу (N + 1). Як результат, це ефективний алгоритм порівняння з лінійним пошуком, але масив повинен бути відсортований перед тим, як здійснювати двійковий пошук.

Програма C щоб знайти елемент з технікою двійкового пошуку.

#включати void main () {int i, прошу, кінець, середина, n, пошук, масив; f ("Введіть кількість елемента n"); scanf ("% d", & n); f ("Введіть% d числа n", n); для (i = 0; i <n; i ++) scanf ("% d", & масив); f ("Введіть номер для пошуку n"); scanf ("% d", & пошук); просити = 0; кінець = n - 1; середина = (просити + кінець) / 2; while (beg <= end) {if (масив <пошук) beg = mid + 1; інакше, якщо (масив == пошук) {f ("Пошук вдалий. n% d знайдено у місці% d. n", пошук, середина + 1); перерва; } else end = середина - 1; середина = (просити + кінець) / 2; } if (beg> end) f ("Пошук невдалий!% d присутній у списку. n", пошук); getch (); }

1. Лінійний пошук носить ітераційний характер і використовує послідовний підхід. З іншого боку, бінарний пошук реалізує підхід розділення та перемоги.
2. Складність часу лінійного пошуку становить O (N), тоді як двійковий пошук має O (log₂N).
3. Найкращий час у лінійному пошуку - це перший елемент, тобто O (1). Навпаки, у двійковому пошуку це стосується середнього елемента, тобто O (1).
4. У лінійному пошуку найгіршим випадком пошуку елемента є N кількість порівняння. Навпаки, це журнал₂N кількість порівняння для двійкового пошуку.
5. Лінійний пошук може бути реалізований як у масиві, так і у пов'язаному списку, тоді як двійковий пошук не може бути реалізований безпосередньо у пов'язаному списку.
6. Як ми знаємо, для двійкового пошуку потрібен відсортований масив, який є причиною. Він вимагає обробку для вставки в потрібне місце для підтримки відсортованого списку. Навпаки, лінійний пошук не вимагає відсортованих елементів, тому елементи легко вставляються в кінці списку.
7. Лінійний пошук простий у використанні, і немає необхідності в будь-яких упорядкованих елементах. З іншого боку, алгоритм бінарного пошуку є складним, і елементи обов'язково розташовані в порядку.

Висновок

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

Типовий алгоритм бінарного пошуку не може бути використаний для пов'язаного списку, тому що зв'язаний список має динамічний характер і невідомо, куди насправді призначений середній елемент. Отже, існує вимога розробити варіацію алгоритму двійкового пошуку, який може працювати і в зв'язаному списку, оскільки двійковий пошук швидше виконується, ніж лінійний пошук.