Binary search (Двоично търсене)

Двоичното търсене е сравнително кратък и прост алгоритъм, който се изпозлва за търсене на някаква стойност в подредена структура от данни (например масив).
Действие:
Интервала, в който се търси съответната стойност, се разделя на половина, т.е. ако търсенето е в масив, се взима средния му елемент. Проверява се дали средния елемент ни удовлетворява. Ако той е търсената стойност, алгоритъма завършва. Ако не е, има два варианта:
1) Ако търсената стойност е по-малка от средния елемент на масива, търсенето продължава в лявата половина на масива, т.е. от първия елемент до елемента, преди средния.
2) Ако търсената стойнос е по-голяма от средния елемент на масива, търсенето продължава в дясната половина на масива, т.е. от елемента след средния, до последния елемент от интервала.
Независимо дали търсенето ще продължи в лявата или дясната половина на масива, отново се намира средния елемент.
Пример:
Ако в масив имаме въведени десет числа (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) и се търси числото 2, на първата стъпка средния елемент ще е 5. Тъй като 5 не съвпада с търсената от нас стойност, алгоритъма продължава да търси в лявата половина, т.е. 1, 2, 3 и 4, защото 2 е по-малко от 5. На следващата стъпка отново се определя средния елемент от числата 1, 2, 3 и 4. Средния елемент е 2. Тъй като той съвпада с търсената от нас стойност, алгоритъма приключва.

40163

Алгоритъма завършва когато търсения елемент е намерен или ако в масива не съществува такъв елемент.

Ето примерен код на двоичното търсене:

using System;

class BinarySearchAlgorithm
{
    static void Main(string[] args)
    {
        Console.Write("Enter array length: ");
        int arrayLength = int.Parse(Console.ReadLine());

        int[] array = new int[arrayLength];

        for (int i = 0; i < arrayLength; i++)
        {
            Console.Write("Index {0} -> ", i);
            array[i] = int.Parse(Console.ReadLine());
        }

        Console.Write("Enter number: ");
        int number = int.Parse(Console.ReadLine());

        Array.Sort(array);
        int left = 0;
        int right = array.Length - 1;
        int middle = 0;
        int index = 0;

        for (int i = 0; i < array.Length-1; i++)
        {
            middle = (left + right) / 2;

            if (number == array[middle])
            {
                index = middle;
                Console.WriteLine("The number index is: {0}", index);
                break;
            }
            if (number < array[middle])
            {
                right = middle - 1;
            }
            if (number > array[middle])
            {
                left = middle + 1;
            }
        }
        if (index != middle)
        {
            Console.WriteLine("There is no such number in the array!!!");
        }
    }
}

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s