Двоично търсене

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Методът двоично търсене се нарича '''Binary Search''' на английски. В литературата и в университета също така може да се срещне като '''Bisection Method''' (метод на бисекцията) или Dichotomy (Дихотомия). В информатикатадвоично търсене е алгоритъм, който се използва за намиране на позицията на елемент или стойност в подредена структура от данни, например в предварително сортиран масив. [1][2] За разлика от последователното търсене, при двоичното търсене са необходими много по-малко стъпки за намиране на търсения елемент. При двоичното търсене, размерът на претърсваното пространство намалява на половина след всяка стъпка. Съществува също така модификация на техниката, при която той намалява само с една трета, но пък решава по-сложен проблем. Тази техника се нарича троично търсене.

Когато искаме многократно да търсим различни елементи в даден масив, е по-добре първо да го сортираме и после да използваме метода на двоичното търсене. Това е бърз метод за претърсване на вече сортиран масив.[3]. Двоичното търсене се основава на разделянето на дадено множество от записи на две равни части, сравняване на търсения идентификатор с последния запис от долната половина или с първия запис от горната половина и установяване по този начин в коя половина се намира той. Следва търсене в така откритата половина чрез нейното разделяне на две части и така нататък докато се стигне до желания запис. По този начин се намалява броят на четенията на записи и се спестява време от тази най-времеемка компютърна операция. Според теория на вероятностите при брой на записите n и последователно търсене средновероятният брой на четенията и свързаните с тях сравнения е n/2. При двоично търсене този брой е значително по-малък. Тъй като, само по себе си, двоичното търсене е сравнително кратко и просто за писане, най-често в задачи то бива съчетано с друг, по-сложен алгоритъм или структура данни. Много често се срещат не малък брой задачи, които се решават (поне частично) с двоично търсене. Този метод е много важен и по друга причина - той е един от популярните въпроси на интервюта за работа. Редица софтуерни компании считат, че ако кандидатът за работно място не може да напише двоично търсене, то няма никакъв смисъл да го наемат като програмист.

Максималният брой стъпки, необходими на алгоритъма за намирането на елемент в сортиран масив, е двоичен логаритъм от дължината на масива. Тоест, за намиране на елемент в сортиран масив от 1 милион елемента алгоритъмът ще извърши най-много 20 стъпки. На всяка стъпка алгоритъмът сравнява търсената стойност със стойността на средния елемент от масива. В случай че средният елемент съвпада с търсения елемент, тогава алгоритъмът завършва – елементът е намерен и неговият индекс (позиция) се връща.[4]

Общ преглед[редактиране | редактиране на кода]

Търсене в сортиран масив е стандартна задача. Речникът, например, е сортиран списък от дефиниции на думи. Търсене на конкретна дума ще намери определението за нея. Телефонен указател е сортиран списък от имена, адреси и телефонни номера. По името на даден човек може да се намери неговият адрес и номер.

Ако списъкът, по който да се зададе търсенето, съдържа повече от няколко артикула (например дузина), двоичното търсене ще отнеме много по-малко сравнения от линейното търсене, но списъкът трябва да бъде сортиран.[4]

Стандартният подход при решаването на сходни проблеми е да се почне от началото – 1, 2, 3 [...] , и да се сравнява всяко едно от числата с търсената стойност. Но ако числата са 100 000, търсенето ще продължи твърде дълго. Същото важи и ако се започне от края на масива, 100 000, 999 999, 999 998 […] , защото търсенето число може да е 1. При двоичното търсене размерът на претърсвания интервал намалява на половина при всяка стъпка, и така времето за решаване на задачата се съкращава драстично.

Двоично търсене на елемент, равен на зададена стойност[редактиране | редактиране на кода]

При многократно търсене на различни елементи в даден масив е по-добре първо да го сортираме и след това да използваме двоично търсене. Сложността, с която се претърсва масив от в от n елемента, е Θ(log(n)).

Започва се с целия масив. Сравнява се търсената стойност с елемента, който е по средата на масива. Възможни са следните три случая:

  • стойностите са равни – търсеният елемент е намерен;
  • търсената стойност е по-малка – търсенето продължава в левия подмасив;
  • търсената стойност е по-голяма – търсенето продължава в десния подмасив.

След това по същия начин се търси в подмасива, после в негов подмасив и т.н. Процесът продължава до намиране на търсения елемент или до подмасив от нито един елемент (масивът не съдържа търсената стойност).

Примери[редактиране | редактиране на кода]

Двочино търсене. Пример 1
Двоично търсене
Двоично търсене. Пример 2

Пример 1[редактиране | редактиране на кода]

Ако в дадена колекция имаме десет числа ( 9, 7, 6, 4, 3, 2, 1) и търсим числото 6, на първата стъпка средния елемент ще е 4. Тъй

като 4 не съвпада с търсената от нас стойност, алгоритъмът продължава да търси в лявата половина, т.е. 9, 7, и 6. На следващата стъпка отново се определя средният елемент, който е числото 7. Той е по-голям от търсената стойност. Всички числа в ляво се елиминират и остава елементът 6. Тъй като той съвпада с търсената от нас стойност, алгоритъмът приключва.

Алгоритъм, основаващ се на тази идея, е реализиран като функция от логически тип, която връща стойност True или False, в зависимост от това дали в масива е намерен или не е намерен елемент, равен на зададения.[5]

Пример 2[редактиране | редактиране на кода]

Още един, подобен на по-горе изложения от нас, пример. Масивът, в който ще търсим, е: list = [1, 4, 10, 12, 15, 20, 22]. Стойността, която трябва да намерим е: num = 10.

Започваме търсенето на num като първо го сравняваме с числото, намиращо се в средата на масива – 12. 10 е по-малкото от 12. Започваме търсенето с числата намиращи в лявата от 12 част от масива: 1, 4, 10.

Първо сравняваме 10 с 1. Търсеното число не е намерено.

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

Сравняваме числото num със следващото число – 10. Числото num e равно на числото от масива. Така намираме num.

Двоично търсене в масив; алгоритъм, изискващ двоични логаритми.

Игра познай номера[редактиране | редактиране на кода]

Тази, на пръв поглед лесна игра, започва с нещо като: „Мисля си едно целочислено число между 40 и 60 включително, а ти трябва да го познаеш. Аз ще казвам „нагоре“, „надолу“ или „да!“.“

Да предположим, че N е числото от възможни стойности (в нашия пример 21 възможни примера ), и тогава (log2 N) въпроси са нужни, за да се определи числото, тъй като всеки въпрос разделя търсеното място. Обърнете внимание, че един въпрос (повтаряне/итерация) по-малко е нужен отколкото за обикновения алгоритъм, защото номерът вече се намира в определени рамки.

Дори ако числото, което трябва да познаем, е произволно (без да имаме горна граница за N), то може да бъде намерено чрез 2(log2 N) + 1 стъпки (N е търсеното число), намирайки първо горната граница с едностранно търсене (или експоненциално търсене – търсене в масив, започвайки от определена начална точка, при което търсеният елемент или се очаква да се намира близо до началната точка или горната (долната) граница са неизвестни)[6]. Например, ако търсеното число е 11, следната последователност може да бъде използвана, за да бъде то намерено: 1 (нагоре), 2 (нагоре), 4 (нагоре), 8 (надолу), 16 (надолу), 12 (надолу), 10 (нагоре). Сега знаем, че числото трябва да е 11, защото е по-голямо от 10 и по-малко от 12.

Можем също да разширим метода на търсене, добавяйки отрицателна стойност. Например, за да намерим -13, може да ползваме следното търсене:  0, −1, −2, −4, −8, −16, −12, −14.

Следващия пример, който ще разгледаме е: да предположим, че имаме сортиран масив [1,2,3,4,5,6,7] и искаме да намерим числото 6, намиращо се на 5 позиция в масива.

Първо трябва да намерим стойността на log N, която ще ни бъде полезна при сравняването на елементите и при избиране на правилната част от масива, в която ще бъде търсено. Можем да използваме while цикъл:

 
int getLogOf(int N)
{
    int log2 = 0
    while((1 << log2) <= N)log2++;
    return --log2;
}

След това можем да започнем търсенето:

 
int find(int array[], int N, int K)
{
    int log2 = getLogOf(N);
    int currentPosition = 0;
    while(log2 >= 0)
    {
       // check if we got a solution
       // if yes, the return it
       if(array[curPosition] == K)
           return curPosition;
       // check the next postion
       int newPosition = curPosition + (1 << log2);
       // if it's smaller or equal then we have to
       // update the current position
       if(newPosition < N && array[newPosition] <= K)
           curPosition = newPosition;
       // decrement the skip size
       log2--;
    }
return -1;
}

Имаме масив [1,2,3,4,5,6,7] и търсим числото 6. Тъй като дължината на масива е 7, то стойността на log 2 от 7 е 2 (2^2 = 4, 2^3 = 8 – взимаме по-малката стойност). Нека да видим как преминава търсенето:

Iter1: [1,2,3,4,5,6,7]

log=2, currentPosition = 0, newPosition = 0 + 2 ^ 2 = 4, array[newPosition] = 5 < 6

currentPosition = newPosition 

log--

Iter2: [1,2,3,4,5,6,7]

log=1, currentPosition = 4, newPosition = 4 + 2 ^ 1 = 6, array[newPosition] = 7 > 6

log--

Iter2: [1,2,3,4,5,6,7]

log=1, currentPosition = 4, newPosition= 4 + 2 ^ 0 = 5, array[newPosition] = 6 == 6

return 5

Така намираме търсеното число.

Имплементиране[редактиране | редактиране на кода]

Имплементацията е проста и сравнително стандартна, в следствие на което много често се ползва един и същ шаблон винаги, когато се пише "байнъри". Първо, тъй като се търси нещо в някакъв интервал, е хубаво да си представим интервала по някакъв начин. Често се търси нещо в масив, като интервалът ще бъде представен чрез най-левия и най-десния валиден индекс. Понякога, обаче ще имаме друга функция, в която се търси отговора. 

За сега ще се разгледат само дискретни функции (тоест такива, които имат краен брой елементи), като например интервал от цели числа или индекс в масив.

Интервала може да се представи чрез две числа - най-лявата (малката) възможна стойност на интервала и най-дясната (голямата) такава, които се наричат left и right или за по-кратко l и r. На всяка стъпка ще се изчислява една нова стойност - средата на интервала - в променлива mid или m. За да се намери средата на интервал по принцип се взима левия му край и се прибавя половината. Това, като код е:

mid = left + (right - left) / 2

По-често, обаче, се ползва малко по-кратък метод на записване на същото нещо: mid = (left + right) / 2

Трябва да се внимава за "overflow" ако се използва съкратения вариант! Дори целият интервал да се събира в даден тип, то сумата на лявата и дясната граница може да не се събира. Например, какво става ако има интервала [1, 2000000000], границите са от тип int (съвсем логично, тъй като типът поддържа този интервал) и се използва int mid = (left + right) / 2;? Ако отговорът е близък до горната граница, ще има стъпки, в които (left + right) ще прехвърли възможностите на int и програмата ще даде грешен резултат. В това отношение по-дългият запис е по-безопасен, тъй като няма този проблем.

До кога се върти цикъла? Това частично зависи от задачата, но най-често при дискретния вариант - докато интервалът съдържа поне един елемент. Това лесно се изразява чрез while цикъл - например най-често се среща while(left <= right) или while(left < right), в зависимост от предпочитанията. 

Примерна имплементация с цикъл[редактиране | редактиране на кода]

C#[редактиране | редактиране на кода]

int binarySearch(int[] array, int value, int left, int right)
{
    while (left <= right)
    {
        int middle = (left + right) / 2;
        if (array[middle] == value)
        {
            return middle;
        }
        else if (array[middle] > value)
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
     }
     return -1;
}

Visual Basic[редактиране | редактиране на кода]

Function BinarySearch(ByVal A() As Integer, ByVal value As Integer) As Integer
    Dim low As Integer = 0
    Dim high As Integer = A.Length - 1
    Dim middle As Integer = 0
 
    While low <= high
        middle = (low + high) / 2
        If A(middle) > value Then
            high = middle - 1
        ElseIf A(middle) < value Then
            low = middle + 1
        Else
            Return middle
        End If
    End While
 
    Return Nothing
End Function

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
    }
}

Горните имплементации, макар и чудесен пример за двоично търсене като цяло, не са хубави пример за различни негови имплементации, тъй като има само един единствен валиден отговор, който, очевидно, е и оптимален. В следващата задача ще има много стойности, които изпълняват изискването на задачата, но само една от тях ще е "оптимална".

Даден е сортиран масив с N (по-малко или равно на 1,000,000) цели числа числа с абсолютна стойност по-малка или равна на 1,000,000,000. Да се намери индекса на най-малкия негов елемент, който е по-голям или равен на дадено цяло число X, отново по-малко или равно на 1,000,000,000 по абсолютна стойност. Ако такъв индекс не съществува, да се върне N.

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

* С обновяване на отговора [редактиране | редактиране на кода]

При този тип има много по-малко мислене какви да са границите и дали да имам <= или < в while() цикъла. Този тип често се предпочита, тъй като е по-труден за объркване. Идеята му е да има допълнителна променлива (ans) за отговора, която се променя всеки път, когато се срещне "хубав" отговор.

int binarySearch(int* array, int arraySize, int x) {
    int ans = arraySize;
    int left = 0, right = arraySize - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] < x)
            left = mid + 1;
        else
            right = mid - 1, ans = mid;
    }
}

* С използване на една от границите [редактиране | редактиране на кода]

Друг вариант, който се среща е да се използва една от границите за "отговор". Ако се погледне внимателно горния код ще се забележи, че след излизане от while() цикъла, променливата right ще е отговорът минус едно.

int binarySearch(int* array, int arraySize, int x) {
    int left = 0, right = arraySize -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right + 1;
}

Интересно е, че всеки път, когато се открие валиден отговор (тоест индекс, чиято стойност е по-голяма или равна на X), се намалява right така, че да е с единица по-малко от това число. Така се гарантира, че последният намерен валиден отговор (съответно и най-малкият такъв) е със стойност right + 1.

Това, обаче, не е много универсална конструкция. Например, ако се търси най-големия индекс, който е по-малък или равен на X. Тогава щеше да се променя left всеки път, когато се намери валиден индекс, като отговорът накрая щеше да бъде в left - 1.

Като цяло, и при двата подхода най-важното е, дали стойността в средата дава валиден (по някакви критерии) отговор или не. При първия вариант в този if (ако стойността е валидна), освен, че се мести границата, се обновяваме и отговора. При втория вариант трябва да се върне границата, която се мести във въпросния if (с +1 или -1, в зависимост дали е right или left).

Малко предимство на първия вариант е, че ако се връща някаква по-странна стойност, ако не се намери отговор (примерно ако се връща -1 вместо N, в горната задача), то щеше да се инициализира ans с -1 в началото (вместо с N), като нямаше да се променя нищо по шаблона. При втория вариант трябва да се внимава за това и да се добави допълнителен if, за да се справим с този случай.

Примерна имплементация с псевдокод[редактиране | редактиране на кода]

function binarySearch(a, value, left, right)
    if right < left
        return not found
    mid := floor((right-left)/2)+left
    if a[mid] = value
        return mid
    if value < a[mid]
        return binarySearch(a, value, left, mid-1)
    else
        return binarySearch(a, value, mid+1, right)

Примерна имплементация с рекурсия[редактиране | редактиране на кода]

C#[редактиране | редактиране на кода]

static int BinarySearchRecursive(int[] array, int value, int low, int high)
{
    if (high < low)
    {
        return -1;
    }
    int middle = (low + high) / 2;
    if (array[middle] > value)
    {
        return BinarySearchRecursive(array, value, low, middle - 1);
    }
    else if (array[middle] < value)
    {
        return BinarySearchRecursive(array, value, middle + 1, high);
    }
    else
    {
        return middle;
    }
}

Visual Basic[редактиране | редактиране на кода]

Function BinarySearch(ByVal A() As Integer, ByVal value As Integer, ByVal low As Integer, ByVal high As Integer) As Integer
    Dim middle As Integer = 0
 
    If high < low Then
        Return Nothing
    End If
 
    middle = (low + high) / 2
 
    If A(middle) > value Then
        Return BinarySearch(A, value, low, middle - 1)
    ElseIf A(middle) < value Then
        Return BinarySearch(A, value, middle + 1, high)
    Else
        Return middle
    End If
End Function

C++[редактиране | редактиране на кода]

C++ разполага с темплейт-базирано бинарно търсене в стандартната си библиотека. Също и функцията bsearch, наследена от C.

    <<array binary search>>=  
    template< typename T, typename compare_less >  
    int array_binary_search(T a[], int low, int high, T target) {  
        while (low <= high) {  
            int middle = low + (high - low)/2;  
            if (compare_less(target, a[middle]))  
                high = middle - 1;  
            else if (compare_less(a[middle], target))  
                low = middle + 1;  
            else  
                return middle;  
        }  
        return -1;  
    }

PHP[редактиране | редактиране на кода]

  function BinarySearch( $array, $key, $low, $high )  
{  
    if( $low > $high ) // termination case  
    {  
        return -1;  
    }  
 
    $middle = intval( ( $low+$high )/2 );  
 
    if ( $array[$middle] == $key ) 
    {  
        return $middle;  
    }  
    elseif ( $key < $array[$middle] ) 
    {  
        return BinarySearch( $array, $key, $low, $middle-1 );  
    }     
 
    return BinarySearch( $array, $key, $middle+1, $high ); 
}

Изисквания и особености[редактиране | редактиране на кода]

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

До сега се говореше предимно за сортирани масиви. Какво е характерното? Нека се разгледат връщаните стойности (отляво надясно), ако се изчислят за всички стойности на началния интервал.

  • В случая с търсенето на най-малкия индекс в сортиран масив, чиито елемент е по-голям или равен на X, то до едно време отговорът е отрицателен, после става положителен (и остава такъв до края на интервала).
  • В случая с търсенето на най-големия индекс в сортиран масив, чиито елемент е по-малък или равен на X, то до едно време отговорът е положителен, после става отрицателен (и остава такъв до края на интервала).

При това, интервалът бива разделен на две части - една със само положителни отговори и една със само отрицателни отговори. Бинарна (true/false) функция, чиито отговори са в началото само положителни (отрицателни), а после само отрицателни (положителни) се нарича монотонна. Техниката "двоично търсене" работи само при такива функции!

Много често отговорите за различни стойности на интервала няма да са въобще бинарни, но с операторите <, >, ≤, ≥ или други критерии могат да се сведат до такива.

Работа с непрекъснат интервал[редактиране | редактиране на кода]

Всъщност, двоичното търсене изобщо не е ограничено до масиви или дискретни стойности. Стига да има начин, по който да се свеждат отговорите от "питанията" на всяка стъпка до монотонна двоична функция, то няма проблем да се работи и с интервал от реални числа. Единствената разлика е, че броят стъпки е по-сложен за определяне (на теория трябва да е безкрайност). Все пак, във всички състезателни и практически задачи отговорът се изисква с някаква точност (примерно 9 знака след десетичната точка), което прави броя възможни стойности краен.

Да се напише функция, която намира корен трети на дадено неотрицателно реално число N.

Какъв ще е критерият за двоичното търсене? Търси се такова число X, за което е изпълнено, че X * X * X = N. Нека се разгледат възможните стойности на X, които са реалните числа в интервала [0, +INF). Колкото по-гоялмо е X, толкова по-голямо е произведението X * X * X. Следователно, тъй като N е неотрицателно, може да се твърди, че до едно време X * X * X ще е по-малко или равно на N, а след това ще е по-голямо. Целта е да се намери най-голямата стойност на X, за която е изпълнено, че X * X * X <= N. Тази функция очевидно е бинарна и монотонна, следователно двоично търсене ще работи. Стига се до първата уловка в задачата. В какви граници ще бъде X? Както се спомена, интервалът е [0, +INF), но тъй като не може (лесно) да се представи положителна безкрайност, то трябва да се сложи някаква стойност. Ползването просто на някакво много голямо число, обаче, не е хубава идея, тъй като каквато и да е тази стойност, N може да бъде тази стойност на трета степен плюс едно, като така би се генерирал грешен резултат. Тъй като горният вариант (ползващ константа) дава дефекти от това, че N може да е произволно голямо, то е логично да се нагласят границите, ползвайки самото N. Стигайки се до този извод, интуитивно [0, N] звучи като добра идея. Всъщност, обаче, не е. Тъй като N е реално число, то спокойно може да бъде, примерно, 0.5, в който случай отговорът ще е по-голям от него. Това е частен случай, за който трябва да се допълнителни усилия. С малко внимание се вижда, че отговорът е в интервала [0, max(N, 1.0)], което вече е добре. Втората уловка е, че след като се провери средата на интервала, не може да се сложи left = mid + 1 или right = mid - 1, както се прави при дискретния вариант. Вместо това се използва left = mid и right = mid. Това, обаче, "чупи" условието на цикъла while (left <= right). Тъй като се сравняват реални числа, има случаи, в които това никога няма да стане. На теория, всъщност, би трябвало никога да не се случи, тъй като mid е винаги между двете и никога точно равно на което и да е от тях (ако в началото left != right). Често този проблем се решава чрез използването на т.н. "епсилони" - тоест много малко число, което се прибавя или изважда за да се елиминира този проблем. Например, би било донякъде интуитивно да се ползваме едно от:

  • while(left + 0.000000001 < right)
  • left = mid + 0.000000001
  • right = mid - 0.000000001

Това решава горния проблем, но създава нов такъв. Какво се случва, ако N = 10-40? Най-вероятно няма да се намери точния отговор, тъй като цикълът ще спре много преди да се стигне до него. Това важи за произволен "епсилон", който се използва. Понякога задачите не разрешават толкова малък вход или биха зачели намерения с тази модификация отговор за верен, но за съжаление не всички са такива, и, съответно, това не винаги работи.

За радост има лесно решение, което се справя и с двата проблема (и, на всичкото отгоре, дава допълнителна сигурност). Знае се, че двоичното търсене работи за логаритъм на брой стъпки. Защо, тогава, да не се направи логаритъм на брой стъпки? Замества се while(left <= right) цикъла с for(int iter = 0; iter < 100; iter++) такъв. Всичко останало вътре в него остава същото. Накрая отговорът ще е left и right, едновременно. Това е така, тъй като след сто итерации техните стойности ще са толкова близки една до друга, че на практика няма да има разлика. Допълнителното предимство е, "сигурността" колко итерации точно ще бъдат направени, като така може да се апроксимира точно необходимото време за изпълнение на програмата.

Така кодът, който може да се ползва за горната задача, би могъл да бъде:

double cubeRoot(double num) {
    double left = 0, right = max(num, 1.0);
    for (int iter = 0; iter < 100; iter++) {
        double mid = (left + right) / 2.0;
        if (mid * mid * mid < num)
            left = mid;
        else
            right = mid;
    }
    return right;
}

Още примери[редактиране | редактиране на кода]

"Рандом" генератор чрез монета[редактиране | редактиране на кода]
Имате на разположение генератор на случайни булеви величини (true, false), или с други думи - монета. Измислете начин, по който можете да генерира случайни реални числа в интервала [0, 1]. Докажете, че генерираните числа са равномерно разпределени.

Прави се "двоично търсене" на числото. На всяка стъпка се разделя останалия интервал на две равни части, и в зависимост от това дали се падне "ези" или "тура" се запазва само лявата или само дясната част. Така, след определен брой хвърляния, останалият интервал ще е толкова малък, че можем да се счете за едно единствено число. Нека, например, при "ези" се взима лявата страна, а при "тура" се взима дясната. Нека също така са се паднали в този ред: ези, тура, ези, ези, тура, ези, тура, тура, тура, ези, тура. Алгоритъм, който се използва, би стеснил интервала по следния начин: [0, 1] -> [0, 0.5] -> [0.25, 0.5] -> [0.25, 0.375] -> [0.25, 0.3125] -> [0.28125, 0.3125] -> [0.296875, 0.3125] -> [0.3046875, 0.3125] -> [0.3046875, 0.30859375] -> [0.306640625, 0.30859375]. В крайна сметка може да се вземе просто средата на останалия интервал, в случая 0.3076171875 и да се каже, че това е търсеното случайно число. Разбира се, прилагането на повече итерации ще постигнали значително по-голяма точност. Този метод можем да се разгледа и по следния начин. В началото се образува редицата 0.5, 0.25, 0.125, 0.0625, 0.03125, … За всеки член от тази редица се хвърля монетата, и ако се падне тура, той се добавя в сумата (която първоначално е била нула). Ако тази редица е безкрайна, резултатното число би било напълно случайно, равномерно разпределено в интервала [0, 1].  

Липсващо число в сортиран масив[редактиране | редактиране на кода]
Даден ви е сортиран масив с N числа между 0 и N, включително, без повтарящи се числа, сортирани в нарастващ ред. Как бихте намерили лиспващото число?

Тази задача почти крещи "binary search, binary search". Винаги, когато има нещо сортирано, трябва да се погледне защо се дава сортирано. Една от възможностите е да се приложи двоично търсене (както е и в случая). На всяка стъпка от двоичното търсене ще се проверява дали на m-та позиция (където m е средата на текущо-разглеждания интервал) стои числото m. Ако не, то липсващото число е или на тази позиция, или наляво. Ако ли пък е, то значи липсващото число е на индекс, по-голям от m.

Прасета и отрова[редактиране | редактиране на кода]
Готвачът на краля приготви 1000 гозби за неговата сватба! Но кралските шпиони му съобщиха, че някой е сипал отрова в точно една от гозбите му. Отровата започва да се забелязва 2 часа след поемане на храната, а до сватбения пир остават... малко повече от два часа - тоест има време точно за една проба. За щастие, готвачът има на разположение известен брой прасета, върху които може да експериментира. На всяко от тях той може да забърка смесица от една или повече от гозбите и му я даде да я изяде. Така ако до два часа прасето умре, то в някоя от гозбите, които е изяло, е имало отрова. За да не става свинщина, той иска да ползва възможно най-малко на брой прасета. Колко е минималният такъв брой, който позволява да се определи в коя гозба е отровата в рамките на тези 2 часа?


Примерно решение е да даде на 1000 прасета по точно една от гозбите, но има решение с много по-малко на брой. Забележете, че той гледа да минимизира не броя умрели прасета, а броя ползвани такива.

Тази задача е значително по-хитра и нетривиална. Отговорът е 10 прасета (двоичен логаритъм от 1000). Тук по-скоро ще се използва идеята на двоичното търсене, а не самия алгоритъм. Готвачът ще даде на първото прасе от всяка от пърата половина от гозбите. На второто прасе ще даде от всяка от първата и третата четвъртина от гозбите. На третото ще даде от 1-вата, 3-тата, 5-тата и 7мата осмина от гозбите и т.н. За да е по-нагледно какво се прави, нека се считам, че броят гозби е само 32 (но същата идея работи за произволен брой). Тогава (представено чрез битови маски, 1 за "даваме", 0 за "не даваме"), всяко от 5-те ни нужни прасета ще получи:

  • Прасе 1: 11111111111111110000000000000000
  • Прасе 2: 11111111000000001111111100000000
  • Прасе 3: 11110000111100001111000011110000
  • Прасе 4: 11001100110011001100110011001100
  • Прасе 5: 10101010101010101010101010101010

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

Намиране на корен на уравнение[редактиране | редактиране на кода]
Дадено е уравнение от типа A*X^5 + B*X^4 + C*X^3 + D*X^2 + E*X + F = 0, където A, B, C, D, E, и F са ненулеви, цели числа, с абсолютна стойност по-малка или равна на 100. Да се намери стойност на X, която го удовлетворява (тоест да се намери някой от корените на уравнението). Например, възможно решение за 3*X^5 - 13*X^4 - 42*X^3 + X^2 + X + 42 = 0 би било -2.297692476.

Това е пример за задача, в която трябва да се направи специално наблюдение защо двоичното търсене би работело.

Основното наблюдение, което ще се използва за да се реши задачата, е, че лявата част от уравнението ще има различни знаци, когато X клони към минус безкрайност и когато клони към плюс безкрайност. Това е вярно, защото коефициентите са ненулеви и съответно най-старшият член A*X^5 променя знака си при отрицателен и положителен X. Следователно, някъде функцията приема стойност 0 (където и сменя знака си). С двоично търсене ще се намери тази точка.

Първо, нека се провери дали има монотонност. В минус безкрайност функцията приема отрицателна стойност. В нула функцията приема положителна стойност (42). В едно функцията приема отрицателна стойност (-8). В плюс безкрайност функцията приема положителна стойност. Отрицателна, положителна, отрицателна, положителна. Очевидно не е монотонна. И все пак в случая може да се използва двоично търсене. Тъй като се търси който и да е от отговорите, а във всеки интервал, в който функцията е с различни знаци в двата му края, има поне един корен. Следователно, рано или късно ще се стигне до подинтервал, в който функцията е монотонна. 

Следва да се намери интервала, в който ще се намират отговорите (или поне един от тях). Тъй като коефициентите на полинома са сравнително малки и при това цели, то може да се докаже, че тя ще има различен знак при X = -1,000,000,000,000 и X = +1,000,000,000,000. Следователно, това са хубави стойности за лява и дясна граница.

Остава да се направи двоично търсене в този интервал, като се мести тази граница, в която функцията има същия знак като в средата на интервала. Не трябва да се забравя да се използва фиксиран брой итерации, вместо стандартната while(left <= right) конструкция!

#include <cstdio>
const double INF = 1000000000000.0;
double eval(int A, int B, int C, int D, int E, int F, double X) {
    return (((( A * X + B) * X * C) * X * D) * X * E) * X + F;
}
int sign(double num) {
    return num < 0.0 ? -1 : 1;
}
 
double solve(int A, int B, int C, int D, int E, int F) {
    double left = -INF, right = INF;
    double ansLeft = eval(A, B, C, D, E, F, left);
    for (int iter = 0; iter < 100; iter++) {
        double mid = (left + right) / 2.0;
        double val = eval(A, B, C, D, E, F, mid);
        if (sign(val) == sign(ansLeft))
            left = mid;
        else
            right = mid;
    }
    return right;
}
 
int main(void) {
    int A = 3, B = -13, C = -42, D = 1, E = 1, F = 42;
    fprint(stdout, "%+d*X^5 %+d*X^4 %+d*X^3 %+d*X^2 %+d*X %+d has root %.9lf\n",
           A, B, C, D, E, F, solve(A, B, C, D, E, F));
    return 0;
}

[7][8][9][10]

Източници[редактиране | редактиране на кода]

  1. Cormen, Thomas H.Leiserson, Charles E.Rivest, Ronald L. (1990).Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
  2. Weisstein, Eric W.„Binary Search“MathWorld.
  3. Светлин Наков и колектив, Програмиране за .NET Framework – том 1
  4. а б Binary search algorithm
  5. https://itplamen.wordpress.com/2013/08/05/binary-search-%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE-%D1%82%D1%8A%D1%80%D1%81%D0%B5%D0%BD%D0%B5/
  6. Binary search algorithm, Number guessing game
  7. http://www.informatika.bg/home - Сайт за алгоритми, състезателна информатика и програмиране
  8. http://stevekrenzel.com/articles/newtons-law
  9. http://en.wikipedia.org/wiki/Binary_search_algorithm
  10. https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/