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

Методът двоично търсене се нарича 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

Ако в дадена поредица имаме седем числа (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 възможни примера), и тогава (log₂ N) въпроси са нужни, за да се определи числото, тъй като всеки въпрос разделя търсеното място. Обърнете внимание, че един въпрос (повтаряне/итерация) по-малко е нужен отколкото за обикновения алгоритъм, защото номерът вече се намира в определени рамки.

Дори ако числото, което трябва да познаем, е произволно (без да имаме горна граница за N), то може да бъде намерено чрез 2(log₂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--

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

log=0, 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. Тоест можем да се определи в коя половина е отровата. В зависимост от това дали второто прасе е умряло, може да се определи в коя четвъртина е отровата. Третото прасе определя осмината и т.н, като последното прасе еднозначно определя отровната гозба.

Намиране на корен на уравнение

		Дадено е уравнение от типа `AX^5 + BX^4 + CX^3 + DX^2 + EX + F = 0`, където `A`, `B`, `C`, `D`, `E`, и `F` са ненулеви, цели числа, с абсолютна стойност по-малка или равна на 100. Да се намери стойност на `X`, която го удовлетворява (тоест да се намери някой от корените* на уравнението). Например, възможно решение за `3X^5 – 13X^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;
}

Източници

↑ 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.
↑ Weisstein, Eric W., „Binary Search“, MathWorld.
↑ Светлин Наков и колектив, Програмиране за .NET Framework – том 1
↑ ^а ^б Binary search algorithm
↑ itplamen.wordpress.com^{[неработеща препратка]}
↑ Binary search algorithm, Number guessing game

Външни препратки

[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

[:0-4] а ^б Binary search algorithm

[5] tplamen.wordpress.com^{[неработеща препратка]}

[6] Binary search algorithm, Number guessing game

[1]

[2]

[3]

[4]

[5]

[6]