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

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

Представьте, что нам надо найти какой-то элемент в массиве. Причем таких запросов может быть очень много (например, поиск товаров в интернет-магазине).

Понятно, что можно «пробегаться» по всем товарам и каждый сравнивать с искомым. Если нашли, то такой элемент в массиве есть, а если перебрали все элементы и не нашли нужный элемент, то он отсутствует. Сложность такого алгоритма О(n).

А можно ли ускорить процесс поиска?

Давайте снова вспомним детство.

Мы часто играли в игру «Угадай число»: один игрок задумывает число от 1 до 100, а второй пытается его угадать за минимальное количество попыток. Причем после каждой попытки вы получаете подсказку «больше» или «меньше». Потом игроки меняются. А разницу в количестве попыток у нас «выдавали» щелбанами. Их получать не очень хотелось, поэтому был стимул угадать быстрее.

А как это сделать? Можно положиться на фортуну и называть числа «наудачу», ни о чем не думая. Но в этом случае может получиться так, что угадаем только с 100 попытки (если не будем повторяться), а это очень больно!

Достаточно быстро появляется следующий алгоритм: называем число 50. Если нам сказали «больше», говорим 75, а если «меньше» - 25. И так далее…

То есть мы каждый раз уменьшаем размер промежутка, в котором находится задуманное число в 2 раза. И за 7 попыток гарантированно угадываем любое задуманное число от 1 до 100.

А как вы думаете за сколько попыток, используя этот метод, можно гарантированно угадать число от 1 до 1000? Всего лишь за 10. Почему?

Каждый раз мы уменьшаем размер промежутка в 2 раза. Это значит, что все завязано на степень числа 2. Находим минимальную степень числа 2, которая больше 100 – это 2^10 = 1024. И значит, за 10 попыток можно угадать любое число от 1 до 1000.

В математике есть такая функция – логарифм: log_{2}1024 = 10. Читается так: в какую степень надо возвести число 2, чтобы получить 1024. Ответ – 10. Понятно, что log_{2}1000 будет больше 9 и меньше 10, но так как количество попыток число целое, округляем его в большую сторону.

Именно поэтому сложность такого алгоритма называют логарифмической О(log n). Логарифмическая сложность алгоритма – это когда на каждом шаге мы делим область поиска как минимум пополам.

Кстати, очень часто стараются ускорить алгоритм, преобразуя его от сложности O (n^2) до О (n log n).

Для понимания: при n=10 000 алгоритм O(n^2) на слабых компьютерах может работать до 100 секунд (100 000 000 операций), а О (n log n) – до 0,14 секунды (10000 * log_{2}10000 – примерно 140 000 операций). Солидная разница, которая при увеличении n увеличивается еще больше!

Делаем вывод: в огромном количестве алгоритмов можно серьезно ускорить процесс поиска, используя так называемый «бинарный поиск». Но… Есть одно но! Чтобы этот поиск работал, массив должен быть обязательно отсортирован!

Бинарный поиск (binary search) – алгоритм поиска индекса элемента в упорядоченном массиве, на каждой итерации происходит деление массива на две части, по этой причине алгоритм называют методом деления пополам.

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

Описание алгоритма бинарного поиска

Алгоритм заключается в следующем:

Определяем значение элемента в середине рабочей области массива данных и сравниваем его с искомым;

Если они равны, возвращаем индекс середины;

Если значение элемента в середине массива больше искомого, то поиск продолжается в левой, от среднего элемента, части массива, иначе в правой;

Проверяем не сошлись ли границы рабочей области, если да - искомого значения нет, нет - переходим на первый шаг.

Пример:

Дан массив целых чисел. Определить, есть ли в массиве введенное число, если да, то на какой позиции оно находится.

Фрагмент кода программы:

int n = 100;
int[] numbers = new int[n];
Random rnd = new Random();
for (int i = 0; i < numbers.Length; i++)
{
    numbers[i] = rnd.Next(1,100);
}

Array.Sort(numbers);

for (int i = 0; i < numbers.Length; i++)
{
    Console.Write(numbers[i]+" ");
}
Console.WriteLine();

Console.WriteLine("Введите искомое число:");
int number = Convert.ToInt32(Console.ReadLine());
int left = 0;
int right = n;
int middle = 0;

while (left != right)
{
    middle = left + (right-left) / 2;
    if (numbers[middle] == number)
    {
        break;
    }
    else if (numbers[middle] > number)
    {
        right = middle;
    }
    else
    {
        left = middle + 1;
    }
    Console.WriteLine("Left: "+left+" Right: "+right);
}

if (numbers[middle] == number)
{
    Console.WriteLine("Число найдено!");
}
else
{
    Console.WriteLine("Поиск завершен. Числа нет!");
}

Задачи и примеры их решения

string[] words = new String[]{"мама", "маме", "маму", "мамы", "мамочка", "мамочке", "мамочку", "мамочки", "мамуля", "мамуле"};

Array.Sort(words);

for (int i = 0; i < words.Length; i++)
{
    Console.Write(words[i]+" ");
}
Console.WriteLine();

Console.WriteLine("Введите слово:");
string word = Console.ReadLine();
int left = 0;
int right = n;
int middle = 0;

while (left != right)
{
    middle = left + (right-left) / 2;
    if (words[middle] == word)
    {
        break;
    }
    else if (string.Compare(words[middle] ,word)>0)
    {
        right = middle;
    }
    else
    {
        left = middle + 1;
    }
}

if (words[middle] == word)
{
    Console.WriteLine("Слово написано правильно!");
}
else
{
    Console.WriteLine("Возможна ошибка! Слова нет в словаре!");
}

int n = 100;
int[] numbers = new int[n];
Random rnd = new Random();
for (int i = 0; i < numbers.Length; i++)
{
    numbers[i] = rnd.Next(1,100);
}

Array.Sort(numbers);

for (int i = 0; i < numbers.Length; i++)
{
    Console.Write(numbers[i]+" ");
}
Console.WriteLine();

Console.WriteLine("Введите рейтинг игрока:");
int number = Convert.ToInt32(Console.ReadLine());
int left = 0;
int right = n;
int middle = 0;

while (left != right)
{
    middle = left + (right-left) / 2;
    if (numbers[middle] == number)
    {
        break;
    }
    else if (numbers[middle] > number)
    {
        right = middle;
    }
    else
    {
        left = middle + 1;
    }
}

Console.WriteLine("Рейтинг противников:");
for (int i=middle-2; i<=middle+3; i++)
{
    Console.WriteLine(numbers[i]);
}

Итоги занятия