Бинарный поиск

Бинарный поиск (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;
}

Смотрите также: