Возможности двоичного поиска

Вы уже пользовались двоичным поиском раньше!

Возникает вопрос: когда вы в последний раз пользовались словарем, как вы находили искомое слово? Вы начали с самого начала и читали каждое слово, пока не нашли то, что искали? Возможно нет.

Это был подход, который вы использовали для навигации по словарю: выберите случайную страницу. Если ваше слово лексографически больше, чем первое слово на этой странице, вы выберете случайную страницу во второй части словаря. Если ваше слово было лексографически меньше, вы выберете страницу в первой половине, в зависимости от того, насколько близко ваше слово. Вы продолжаете делать это, пока не найдете искомое слово.

Вы использовали бинарный поиск, даже не подозревая об этом.

Понимание двоичного поиска

Итак, давайте разберемся с двоичным поиском. Допустим, вы хотите найти элемент в массиве. Не бойтесь массивов. Массивы - это просто списки однотипных данных.

Вам предоставляется следующий массив:

Допустим, вас просят найти позицию 23 в этом массиве. Как ты его найдешь?

Один из подходов - перебрать все элементы в массиве и остановиться, когда вы найдете правильное совпадение. Такой подход верен и позволит найти правильное положение X. Но это не очень быстрый способ найти этот элемент, потому что вы не используете одно из самых полезных свойств массива.

Найдите минутку, чтобы выяснить полезное свойство, которое поможет нам найти X быстрее.

Полезное свойство массива заключается в том, что он отсортирован. То есть следующий элемент в массиве всегда больше предыдущего. Это поможет нам найти элемент намного быстрее с помощью двоичного поиска. Двоичный поиск использует сортированный характер массива и находит элемент намного быстрее. Посмотрим как.

Алгоритм

1. Найдем средний элемент массива. В данном случае это 16, поскольку слева от него 4 элемента, а справа 5 элементов. (Поскольку это массив из четного числа элементов)
2. Сравним 16 с X = 23. Начиная с X ›16, будем смотреть в правую половину массива.
3. Теперь наш массив урезается до 5 элементов.
4. Повторим тот же шаг еще раз: находим средний элемент массива. Это 56. Поскольку _5 _ (= 23) меньше 56, мы будем смотреть в левую половину этого массива.
5. Наконец, наш массив состоит только из 2 элементов: 23 и 38. Средним элементом этого массива будет 23. Сравнивая это с _6 _ (= 23), мы находим, что X = 23. Следовательно, мы нашли элемент в массиве.

Полный алгоритм можно визуализировать ниже, взятый отсюда.

Краткое объяснение для читателей Tech

Мы в основном игнорируем половину элементов сразу после одного сравнения.

1. Сравните X со средним элементом.
2. Если X соответствует среднему элементу, мы возвращаем средний индекс.
3. Иначе Если X больше среднего элемента, то X может находиться только в правой половине подмассива после среднего элемента. Итак, мы возвращаемся к правой половине.
4. Иначе (X меньше) повторяется для левой половины.

Как это сэкономило время?

Если вы не поняли, почему этот алгоритм экономит время, причина в следующем: алгоритм выбрасывает половину текущего массива после каждого сравнения.

Допустим, T (n) - это количество времени, необходимое для поиска элемента в массиве из n элементов. Таким образом, будет выполнено следующее рекуррентное соотношение:

T(n) = T(n/2) + c

Поскольку после одного сравнения он находит элемент в массиве размера n / 2, а также требует постоянного количества времени для сравнения. Решая это рекуррентное соотношение, мы находим, что временная сложность для этого алгоритма равна O (log (N)). Чтобы продемонстрировать, почему это быстрее обычного O (n), это потому, что, когда N продолжает увеличиваться, O (N) значительно увеличивается по сравнению с O (log (N)), как показано на графике ниже. .

Возможности двоичного поиска

Чтобы дать представление о том, насколько быстро работает двоичный поиск, приведем пример: в базе данных, состоящей из 100 000 пользователей, расположенных в алфавитном порядке, вы можете найти имя конкретного пользователя в 10–15 сравнения! Если бы в этом случае использовался алгоритм линейного поиска, в худшем случае потребовалось бы 100 000 сравнений! Я надеюсь, что это демонстрирует силу бинарного поиска и то, почему он так полезен для нас.

Разработчики регулярно используют двоичный поиск для повышения производительности своего приложения и сокращения временных сложностей.

Реализация кода

• Ниже приводится рекурсивная реализация алгоритма, который мы обсуждали выше.
• Ниже приводится итеративная реализация того же самого.

// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;
        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
    // We reach here when element is not
    // present in array
    return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Element is not present in array"
                : cout << "Element is present at index " << result;
    return 0;
}
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;
        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
    // We reach here when element is not
    // present in array
    return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Element is not present in array"
                : cout << "Element is present at index " << result;
    return 0;
}

Заключительные комментарии

• Всегда помните, что двоичный поиск может работать только с отсортированным массивом.
• Надеюсь, вам понравился этот пост. Если да, обязательно подпишитесь на меня в Twitter.
• До следующего раза.