Препоръчано, 2020

Избор На Редактора

Разлика между линейното търсене и двоичното търсене

Линейното търсене и двоичното търсене са двата метода, които се използват в масиви за търсене на елементи. Търсенето е процес на намиране на елемент в списъка на елементите, съхранявани в произволен ред или произволно.

Основната разлика между линейното търсене и двоичното търсене е, че двоичното търсене отнема по-малко време за търсене на елемент от сортирания списък от елементи. Така се заключава, че ефективността на двоичния метод на търсене е по-голяма от линейното търсене.

Друга разлика между двете е, че има предпоставка за двоичното търсене, т.е. елементите трябва да бъдат сортирани, докато при линейното търсене няма такава предпоставка. Въпреки че и двата метода за търсене използват различни техники, които са обсъдени по-долу.

Сравнителна таблица

Основа за сравнениеЛинейно търсенеДвоично търсене
Времева сложностО (N)O (log 2 N)
Най-добър случайПърви елемент O (1)Централен елемент O (1)
Предпоставка за масивНе се изискваМасивът трябва да е в подреден ред
Най-лош случай за N брой елементиНеобходими са N сравненияМоже да завърши само след сравняване на log 2 N
Може да се изпълнява наМасив и свързан списъкНе може да се приложи директно в свързан списък
Включете операциятаЛесно се вмъква в края на списъкаИзисквайте обработка за вмъкване на подходящото място за поддържане на сортиран списък.
Тип алгоритъмИтеративен характерРазделяй и владей в природата
полезностЛесен за използване и няма нужда от поръчани елементи.Всеки сложен алгоритъм и елементи трябва да бъдат организирани по ред.
Редове от кодПо-малко| Повече ▼

Дефиниция на линейното търсене

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

Следователно, линейното търсене може да бъде определено като техника, която преминава последователно последователността на масива, за да се намери дадения елемент. Посочената по-долу програма илюстрира търсенето на елемент от масива чрез търсене.

Ефективност на линейното търсене

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

C Програма за търсене на елемент с линейна техника за търсене.

 #include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("въведете броя на елемента:"); scanf ("% d", & n); printf ("Въведете числата: n"); за (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("Въведете номера за търсене:"); scanf ("% d", & item); за (i = 0; i = 0) {printf ("n% d се намира в позиция% d:", item, loc + 1); } else {printf ("\ t } getch (); } 

Определение на двоичното търсене

Двоичното търсене е изключително ефективен алгоритъм. Тази техника на търсене изразходва по-малко време при търсене на дадения елемент при минимални възможни сравнения. За да направите двоичното търсене, първо трябва да сортираме елементите на масива.

Логиката на тази техника е дадена по-долу:

  • Първо намерете средния елемент на масива.
  • Средният елемент на масива се сравнява с елемента за търсене.

Възможни са три случая:

  1. Ако елементът е задължителният елемент, търсенето е успешно.
  2. Когато елементът е по-малък от желания елемент, търсете само първата половина на масива.
  3. Ако е по-голям от желания елемент, след това потърсете във втората половина на масива.

Повторете същите стъпки, докато не се намери елемент или се изчерпи в областта за търсене. В този алгоритъм, всяка област за търсене на време се намалява. Следователно броят на сравненията е най-много log (N + 1). В резултат на това той е ефективен алгоритъм в сравнение с линейното търсене, но масивът трябва да бъде сортиран преди да се извърши двоичното търсене.

C Програма за намиране на елемент с двоична техника за търсене.

 #include void main () {int i, beg, end, middle, n, търсене, масив [100]; printf ("Въведете номера на елемента n"); scanf ( "% D", и п); printf ("Въведете% d числата n", n); за (i = 0; i <n; i ++) scanf ("% d", & масив [i]); printf ("Въведете номера за търсене n"); scanf ("% d", & търсене); beg = 0; край = n - 1; средата = (beg + end) / 2; while (beg <= end) {if (масив [среда] край) printf ("Търсенето е неуспешно!% d не присъства в списъка. \ t getch (); } 

Ключови разлики между линейното търсене и двоичното търсене

  1. Линейното търсене има итеративен характер и използва последователен подход. От друга страна, двоичното търсене изпълнява подход „разделяй и владей“.
  2. Времевата сложност на линейното търсене е O (N), докато двоичното търсене има O (log 2 N).
  3. Най-добрият случай в линейното търсене е за първия елемент, т.е. O (1). В противоречие с бинарното търсене, то е за средния елемент, т.е. O (1).
  4. В линейното търсене, най-лошия случай за търсене на елемент е N номер на сравнение. За разлика от това, това е log 2 N номер на сравнение за двоично търсене.
  5. Линейното търсене може да бъде реализирано както в масив, така и в свързан списък, докато двоичното търсене не може да се приложи директно в свързан списък.
  6. Както знаем Бинарното търсене изисква сортирания масив, който е причина За обработката е необходимо да се вмъкне на подходящото място, за да се поддържа сортиран списък. Напротив, линейното търсене не изисква сортирани елементи, така че елементите лесно се вмъкват в края на списъка.
  7. Линейното търсене е лесно за използване и няма нужда от подредени елементи. От друга страна, двоичният алгоритъм за търсене е труден и елементите задължително са подредени по ред.

заключение

Както линейни, така и двоични алгоритми за търсене могат да бъдат полезни в зависимост от приложението. Когато масивът е структурата на данните, а елементите са подредени в подреден ред, тогава бинарно търсене е предпочитано за бързо търсене. Ако свързаният списък е структурата на данните, независимо как са подредени елементите, линейното търсене се приема заради липсата на директна реализация на двоичен алгоритъм за търсене.

Типичният двоичен алгоритъм за търсене не може да се използва за свързан списък, тъй като свързаният списък е динамичен характер и не е известно къде всъщност е определен средният елемент. Следователно, съществува изискване да се проектира вариацията на двоичния алгоритъм за търсене, който може да работи и върху свързания списък, защото двоичното търсене е по-бързо в изпълнение от линейното търсене.

Top