Бінарний пошук

Бінарний пошук (binary search) – це алгоритм пошуку індексу елемента у впорядкованому масиві, на кожній ітерації відбувається поділ масиву на дві частини, з цієї причині алгоритм називають методом ділення пополам.

Метод бінарного пошуку достатньо простий для розуміння, водночас він дуже ефективний. Оскільки на кожному кроці кількість елементів в робочій області масиву зменшується вдвічі.

Опис алгоритму бінарного пошуку

Алгоритм полягає в наступному:

• Визначаємо значення елементу посередині робочої області масиву даних і порівнюємо його з шуканим;
• Якщо вони рівні, то повертаємо індекс;
• Якщо значення елементу посередині масиву більше шуканого, то пошук продовжується в лівій частині масиву, інакше в правій;
• Перевіряємо чи не зійшлись межі робочої області, якщо так, то значення не знайдено, ні – переходимо на перший крок.

Рекурсивна реалізація бінарного пошуку

using System;

class Program
{
    //метод для рекурсивного бінарного пошуку
    static int BinarySearch(int[] array, int searchedValue, int first, int last)
    {
        //межі зійшлись
        if (first > last)
        {
            //елемент не знайдено
            return -1;
        }

        //середній індекс підмасиву
        var middle = (first + last) / 2;
        //значення посередині масиву
        var middleValue = array[middle];

        if (middleValue == searchedValue)
        {
            return middle;
        }
        else
        {
            if (middleValue > searchedValue)
            {
                //рекурсивний виклик пошуку для лівого підмасиву
                return BinarySearch(array, searchedValue, first, middle - 1);
            }
            else
            {
                //рекурсивний виклик пошуку для правого підмасиву
                return BinarySearch(array, searchedValue, middle + 1, last);
            }
        }
    }

    //програма для бінарного пошуку елементу у впорядкованому масиві
    static void Main(string[] args)
    {
        Console.WriteLine("Бінарний пошук(рекурсивна реалізація)");
        Console.Write("Введіть елементи масиву: ");
        var s = Console.ReadLine().Split(new[] { " ", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);
        var array = new int[s.Length];
        for (int i = 0; i < s.Length; i++)
        {
            array[i] = Convert.ToInt32(s[i]);
        }

        //сортуємо масив
        Array.Sort(array);
        Console.WriteLine("Впорядкований масив: {0}", string.Join(", ", array));

        while (true)
        {
            Console.Write("Введіть значення для пошуку, або -777 для виходу: ");
            var k = Convert.ToInt32(Console.ReadLine());
            if (k == -777)
            {
                break;
            }

            var searchResult = BinarySearch(array, k, 0, array.Length - 1);
            if (searchResult < 0)
            {
                Console.WriteLine("Елемент зі значенням {0} не знайдено", k);
            }
            else
            {
                Console.WriteLine("Елемент знайдено. Індекс елементу зі значенням {0} рівний {1}", k, searchResult);
            }
        }

        Console.ReadLine();
    }
}

Ітеративна реалізація бінарного пошуку

//метод бінарного пошуку з використанням циклу
static int BinarySearch(int[] array, int searchedValue, int left, int right)
{
    //поки не зійшлись межі робочої зони масиву
    while (left <= right)
    {
        //індекс середнього елементу
        var middle = (left + right) / 2;

        if (searchedValue == array[middle])
        {
            return middle;
        }
        else if (searchedValue < array[middle])
        {
            //звуження робочої зони масиву справа
            right = middle - 1;
        }
        else
        {
            //звуження робочої зони масиву зліва
            left = middle + 1;
        }
    }
    //нічого не знайдено
    return -1;
}