Binary search (двоично/логаритмично търсене) е алгоритъм за намиране на позицията на елемент или стойност в подредена структура от данни, например в сортиран масив. Работи като сравнява търсената стойност със средния елемент на масива (този посредата).
При четни – да кажем броя ти е 8 и са целите числа от 1 до 8 включително=> ще вземе 4-тия елемент като среда.
При нечетни – горната или долната половина на масива се елиминира, в зависимост от резултата и така търсенето се повтаря в останалия вече по-малък масив, докато не приключи.
Да кажем броят е 9 този път -> ще се чуди между 2 стойности (понеже 9/2 = 4.5) и те са 4 и 5. Може или да раздели 9 на 2 и да вземе цялата част (4.5 и маха 0.5 и става 4) или да допълни 4.5 на 5.
В този случай ( с 9) при делене взема 4-ката и така ги разделя на 2 подмасива – един с 3 стойности, друг с 5 (понеже махаме средния).
В другия случай ( допълване до 5) като я вземем 5-цата остават 2 подмасива с равен брой елементи – по 4 във всеки.
Бинарното търсене логаритмично време и прави сравнения на базата на О(log n), където n е броя на елементите в масива, а log – това е бинарен логаритъм; О – голямо о, не нула, и се ползва за класифициране на алгоритмите по това как реагира на промените в размера на входящата информация (input), като например как времето за обработка на един алгоритъм се променя, когато размерът на задачата става изключително голям.
Малко разяснение по „сложността на времето“ (time complexity) – алгоритмите се определят дали са добри или лоши и дали имат добро или лошо логаритмично време като се намери колко време му трябва, за да изчисли една сметанка.
Някои са много добри за малък брой елементи, и много зле с голям брой, други обратно и т.н.
Сложността на времето обикновено се измерва като броим колко елементарни операции се извършват от алгоритъма, където една елементарна операция изисква фиксиран период от време за да се изпълни. В такъв случай, изминалото време и броят на елементарните операции извършени от алгоритъма се различават най-много с някаква константа. Най-дългото време, което може да отнеме на 1 алгоритъм и се води с най-лошата сложност на времето, е T(n).
Има таблици в Интернет с различните алгоритми колко време им отнема.
Обратно към бинарното:
Когато искаме многократно да търсим различни елементи в даден масив, е по-добре първо да го сортираме и после да използваме метода на двоичното търсене. Това е бърз метод за претърсване на вече сортиран масив.
Според теория на вероятностите, при брой на записите n и последователно търсене средновероятният брой на четенията и свързаните с тях сравнения е n/2. При двоично търсене този брой е значително по-малък. Тъй като, само по себе си, двоичното търсене е сравнително кратко и просто за писане, най-често в задачи то бива съчетано с друг, по-сложен алгоритъм или структура данни. Много често се срещат не малък брой задачи, които се решават (поне частично) с двоично търсене. Като цяло този метод е много важен и по друга причина - той е един от популярните въпроси на интервюта за работа, както при теб. Редица софтуерни компании считат, че ако кандидатът за работно място не може да напише двоично търсене, то няма никакъв смисъл да го наемат като програмист, така че трябва да се внимава по тази тема.
Пускам ти 1 код за бинарно търсене на Java:
public class BinarySearch {
//масива в който ще търсим
public static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
public static void main(String[] args){
int elementToFind = 7; //елемента, за който ще търсим
int position = binarySearch(elementToFind, 0, arr.length-1);
if(position == -1)
System.out.println("Елемента не е намерен");
else
System.out.println("Елемента е намерен на позиция "+(position+1));
}
//метод реализиращ двойчно търсене
public static int binarySearch(int element, int left, int right){
int l = left;
int r = right;
int m = (l+r)/2;
while(l < = r){
if(element == arr[m])
return m;
else if(element < arr[m])
r = m - 1;
else
l = l + 1;
m = (l+r)/2;
}
return -1; //ако не е намерен връщаме -1
}
}Това е като цяло, дано да е станало ясно. :) Със сигурност ще ти трябват добри математически умения и най-вече практика, за да ги разбереш напълно.
