Когато започнах да се гмуркам в дълбокия и сложен свят на компютърните науки, бях много уплашен от това, което беше пред мен и огромната дълбочина на всичко това. Едно от първите неща, за които научих, беше алгоритъмът за двоично търсене.
Виждате, че когато пишем алгоритми или набори от инструкции, които нашият компютър да изпълнява, в идеалния случай искаме той да работи възможно най-ефективно и бързо. Един пример би бил алгоритъм за търсене. За нашите цели алгоритъмът ще бъде просто заявка за един елемент в сортирана колекция. Добър пример е запитване към телефонния указател. Търсите човек в телефонен указател и се надявате, че името съществува в телефонния указател. Ако лицето съществува в телефонния указател, тогава имате неговия телефонен номер или позицияв указателя. Сега има два начина, по които можете да направите това; просто търсене или използване на нашия нов инструмент, двоично търсене.
Нека започнем с простото търсене. Ако не сте имали времеви ограничения и не сте имали представа как да намерите този човек в този гигантски набор от записи. Трябваше да преминете през всеки елемент от колекцията, един по един, докато намерите човека, когото търсите... Това би било ужасно, шансовете да намерите този човек навреме са минимални. В най-добрия случай това може да е първият човек или човекът може да е на една от първите няколко страници, но в най-лошия случай това е последният човек на ПОСЛЕДНАТА страница. Така че това наистина е във въздуха и тъй като колекцията от елементи става по-голяма, толкова повече време ще отнеме на заявката да завърши. Ето кодов фрагмент, за да илюстрирате как се случва
Сега нека опитаме двоичното търсене. При двоичното търсене ключът е сортираната колекция. С колекцията, сортираното двоично търсене наистина блести като по-добрият метод за намиране на човека в телефонния указател. С Binary Search отгатвате средното число или елемент в колекцията и елиминирате половината от колекцията, независимо дали елементът е твърде голям или твърде малък. След това повтаряте процеса и непрекъснато стеснявате колекцията, като отгатвате нов среден елемент в новосъкратената колекция и я стеснявате, докато намерите елемента и позицията в колекцията.
Ето кодовия фрагмент:
Изглежда, че се случват много неща, но с този метод вие всъщност много улеснявате намирането на това, което търсите, и то за рекордно кратко време. Присвоявате ниска и висока стойност и ги променяте последователно, докато колекцията става по-малка, и в резултат на това присвоявате нова средна стойност. След това проверявате дали тази нова средна стойност е същата като елемента, който търсите, и връщате средното число. В противен случай преназначете нови високи, ниски и средни стойности и започнете отново. Сортираната колекция улеснява преназначаването на нова средна стойност всеки път.
Сега, след като видяхте и двата метода, надявам се, че ако трябва да напишете прост алгоритъм за търсене, ще го направите с двоично търсене, вместо да преминавате през всеки елемент един по един.
