Алгоритъм за двоично търсене
(Двоичният) алгоритъм за двоично търсене осигурява бързо търсене в сортирани масиви или колекции. Този итеративен подход за търсене игнорира приблизително половината от стойностите в колекцията с всяко преминаване, което позволява мащабируемост.
Когато трябва да намерите позицията на елемент в сортируема колекция, алгоритъмът за двоично търсене осигурява подходящ и бърз подход. Този алгоритъм е включен в общия клас List, който беше въведен в .NET framework версия 2.0. Въпреки че това означава, че обикновено не е необходимо да го пресъздавате, интересно е да разберете как работи този алгоритъм.
Алгоритъмът за двоично търсене е итеративен. По време на всяка итерация избирате централния елемент в масива според неговия индекс. Ако намерената стойност е тази, която търсите, алгоритъмът е завършен. Ако приемем, че масивът първо е сортиран с най-малките стойности, ако стойността в средната точка е по-малка от търсенето на елемента, средната точка и всички елементи, преди да го изхвърлите, намалявайки наполовина размера на останалите елементи. Ако средната стойност е по-голяма от търсения елемент, всички елементи от този индекс до края на масива ще бъдат отхвърлени. Тези елементи могат да бъдат игнорирани, тъй като колекцията е сортирана. Ако не стане, двоичният метод за търсене не работи.
Когато размерът на масива се намали наполовина, процесът се повтаря. Всяка итерация премахва половината от възможните стойности или идентифицира елемента, който искате да намерите. Това продължава, докато елементът бъде намерен или докато всички елементи не бъдат изключени от търсенето, в който момент знаете, че търсеният елемент липсва.
В действителност обикновено е неефективно действителното премахване на елементи от масив или колекция. Много по-вероятно е да използвате указатели къмдефиниции на първия и последния индекс за търсене. Те се инициализират, за да сочат към първия и последния елемент в последователността и един от указателите се премества по време на всяка итерация, за да намали наполовина ефективната дължина на колекцията.
Нека да разгледаме пример, използвайки стойностите по-долу, търсейки числото тридесет и шест.
В първата итерация ще започнем с дефиниране на средата. Тъй като колекцията има четен брой елементи, можем да изберем десетия или единадесетия елемент. Решението е произволно, така че нека използваме най-лявата от средните стойности, която е четиридесет и осем.
Четиридесет и осем е повече от числото, което търсим. Това означава, че всички елементи с по-високи индекси също трябва да са по-големи от тридесет и шест, така че можем да игнорираме по-високата половина на колекцията. След това можем да намерим средата на по-малкия набор от стойности, който е двадесет и девет.
Двадесет и девет е по-малко от числото, което искаме да намерим, така че можем да го игнорираме и всички стойности под него. Това оставя само четири елемента за търсене. Когато намерим средата на тези останали елементи, откриваме, че е тридесет и шест, които сме се заели да намерим. Това означава, че успяхме да намерим двадесет елемента само за три повторения.
Нека внедрим алгоритъм за двоично търсене с помощта на C#. Ще създадем метод за извършване на двоично търсене на сортиран масив от цели числа. Ще приемем, че масивът е сортиран във възходящ ред. Върнатата стойност за метода ще бъде индексът на търсения елемент или -1, ако елементът не е намерен.
За да започнете, добавете следния подпис на метода към класа, който беше автоматично генериран при създаването на проекта. Методът има два параметъра. Първополучава масива за търсене, а вторият получава числото.
Вместо да се опитваме да намалим размера на масива по време на всяка итерация, ще използваме указатели към началото и края на „частта“ от масива, която съдържа елемента, който търсим. В началото на процеса това е целият масив. Следователно началният указател ще сочи към индекс нула, а крайният указател ще бъде по-малък от дължината на масива.
За да настроите указателите и да извикате итеративната част на алгоритъма, добавете следния код към метода SearchBinary:
Рекурсивен метод на търсене
Рекурсивната част на алгоритъма има четири части:
- Уверете се, че началният и крайният указател все още са валидни, като посочите дължина на масива, която е по-голяма от нула. Ако елементът, който търсим, не съществува в масива, след последната итерация началният и крайният указател ще се припокрият, давайки част от масива без елементи. Ако е така, ще върнем -1, за да покажем, че елементът липсва.
- Намерете индекса на средната точка на останалите елементи. Това се изчислява лесно с помощта на началния показалец и дължината на оставащия елемент.
- Проверете дали елементът в средата е стойността, която искаме да намерим. Ако е така, връщаме индекса на средната точка и алгоритъмът приключва.
- Уверете се, че елементът в средата е по-голям от думата за търсене. Ако е така, преместваме крайния указател с един елемент към средата и започваме следващата итерация от стъпка 2 по-горе. Ако не, средната стойност трябва да е по-малка от търсения елемент, така че преместваме началния показалец към елемента точно след средата и се връщаме към стъпка 2.
За да изпробвате алгоритъма за търсене, добавете следния код към главния метод и преминете през кода в програмата за отстраняване на грешки,за да видите резултатите, или добаветеConsole.WriteLine(index);в края.
IT статии, Sea Sharp, алгоритми