Двоично търсене - разбор на алгоритъма в c++

В процес на разработка софтуер масивите се използват навсякъде. "Интелигентни" типове данни в днешните езици за програмиране, като динамичните масиви например, предоставят големи възможности за удобна работа с обекти. Но алгоритмите, които стоят зад тези типове данни, са разработени в началото на компютърните науки - в средата на ХХ век. Първият алгоритъм за двоично търсене е публикуван през 1946 г.

Разгледайте най-популярните алгоритми да работите с с масиви.

Последователно (линейно) търсене

Това е най-простият алгоритъм за намиране на стойност в масив. Използва метод за последователно сравняване на елементите на масива със стойността на ключа. Изпълнени по нормален начин, от ляво на дясно. Използва се, ако в масива има малко елементи или ако списъкът не е подреден. Напълно неефективно в големи масиви, където обикновено се използва двоично търсене. Алгоритъмът работи по следния начин:

• Сравнете стойността на ключа с По стойност на елемент на масив.
• Ако стойностите са равни, върнете стойността.
• Ако не - увеличете променливата на цикъла с единица и я сравнете със следващия елемент на масива.

индексно-последователно търсене

По-ефективен начин за намиране на стойност в сортиран масив. Но тя изисква повече ресурси.

Бинарно търсене

Бинарното търсене е алгоритъм за намиране на елемент от масив чрез последователно разделяне на масива наполовина и сравняване на началното число с числото в средата на масива. Ако числото от средата е по-малко от необходимата стойност, продължаваме търсенето във втората част; ако е по-голямо, продължаваме търсенето в първата част. Този алгоритъм е най-бързият от всички и работи по следния начин:

• Първо намираме стойността на обекта в средата на масива. Проверка за съвпадение с първоначалната стойност.
• Ако стойността от средата е по-малка от първоначалната, продължаваме търсенето във втората половина; ако е по-голяма, търсим в първата половина.
• Разделяме половината в масива и сравняваме получената стойност.

Търси, докато оригиналната стойност е равна на стойността на масива. Ако това не се случи - значи тази стойност не е в масива.

При проектирането на двоично търсене могат да се срещнат няколко подводни камъка.

Препълване на избрания тип данни

За да намерите стойността в средата на масив, съберете дясната и лявата стойност и разделете на две. Тоест:

Средна стойност на масива = лява стойност + (лява стойност - дясна стойност)/2

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

Грешки в стойностите

Или една грешка. Много е важно да разгледате следните възможности:

• Празен масив.
• Няма стойност.
• Извън обхвата.

Множество случаи

Обърнете внимание, че ако в масива има няколко еднакви екземпляра на ключа, програмата трябва да намери конкретен такъв (първи, последен, следващ).

Нека видим реализация на този алгоритъм на езика за програмиране C plus. Обърнете внимание, че двоичното търсене работи само със сортиран масив! Ако масивът не е предварително сортиран, резултатът от изчислението ще бъде неправилен.

По-долу е кодът на езика C ++. Първо се инициализира масив от целочислени променливи arr с размер десет. След това операторът cin в цикъла for изчаква потребителят да въведе десет стойности (десети ред).

На ред 20 програмата изчаква потребителят да въведе стойността на ключа.

Редове 29 - 35 са реализираният алгоритъм за двоично търсене. По време на изпълнението на програмата стойността на средния елемент се записва в променливата mid, като се използва формулата:

Масив mid = (лява стойност (l) + дясна стойност (r))/2

Редицата е

arr[mid]==ключ

Извършва се проверка дали средната стойност е равна на ключовата стойност. Ако е равна, стойността на променливата флаг се променя на TRUE, т.е. проблемът е решен.

Ако mid е по-голяма от стойността на нашия ключ, дясната част (променливата r) се присвоява на mid. Ако е обратното, mid се поставя в r.

Последното е проверка на булев флаг на променлива.

Предимства на двоичното търсене

Бинарното търсене трябва да се използва, когато искате бърза програма да работи. Написването на такъв алгоритъм не е трудно дори за начинаещ програмист. Но е много важно да се разгледат всички екстремни случаи: превишаване на масива, липсваща стойност, грешка при препълване на данните.

Недостатъци

За да работи алгоритъмът правилно, масивът трябва да е предварително сортиран. Можете да използвате готовата функция sort() в езика за програмиране C++. И има още нещо важно, което трябва да запомните вземете под внимание, изучаване на двоичното търсене в езиците C и C++. Този алгоритъм може да се използва само с определени структури от данни. Например структури, които използват свързани списъци, не се вписват тук.