Поиск — очень распространенное действие в коде. Просто представьте себе веб-сайт электронной коммерции, где вы ищете желаемые товары, которые вы искали на их веб-сайте. А теперь представьте, как бы вы себя чувствовали, если бы загрузка вашего результата заняла вечность и продолжала бы показывать вам полосу загрузки, что было бы очень раздражающим пользователем. Здесь возникает важность эффективных алгоритмов поиска для ускорения процесса поиска. В сегодняшней статье мы рассмотрим два наиболее часто используемых алгоритма поиска в кодировании.

Линейный поиск

Как программист, вы могли использовать этот алгоритм несколько раз, не понимая, что это алгоритм. Да, и название алгоритма — Линейный поиск. Это простейший метод поиска, при котором мы проверяем каждый элемент в структуре данных до тех пор, пока искомый элемент не будет найден. Если после проверки всех элементов искомый элемент не найден, то приходим к выводу, что его нет в структуре данных.

Этот алгоритм не очень широко используется для методов поиска, потому что это не лучший подход для проверки каждого отдельного элемента, который замедляет весь ваш код, делая сложность этого алгоритма в худшем случае O(n). . Но в отличие от бинарного поиска, линейный поиск может быть реализован как в отсортированных, так и в несортированных массивах.

int linear_search(int *array, int size, int user_search)
{
    for (int i = 0; i < size; i++)
    {
        if (array[i] == user_search)
        {
            return i;
        }
    }
    return -1;
};

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

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

Двоичный поиск – это эффективный метод поиска в отсортированных массивах, который начинается с доступа к среднему элементу массива. Если искомый элемент больше среднего элемента, то продолжаем поиск с правой стороны массива от среднего элемента, так как очевидно, что искомый элемент будет с правой стороны, так как искомый элемент больше среднего. средний элемент, и массив тоже отсортирован. Если элемент поиска меньше среднего элемента, то продолжаем поиск с левой стороны. Теперь возникает вопрос, как долго мы будем продолжать этот процесс. Мы продолжаем процесс поиска до тех пор, пока средний элемент не будет равен искомому элементу, а затем, если он равен среднему элементу, мы возвращаем индекс среднего элемента. Но что, если элемент не существует в массиве? Помня об этом случае, мы продолжаем поиск только до тех пор, пока нижняя граница меньше или равна верхней границе. Нижняя граница — это нижний индекс массива, а верхняя граница — это самый высокий индекс текущего искомого массива.

int binarySearch(int array[], int user_search, int low, int high)
{
    if (low <= high)
    {
        int mid = (low + high) / 2;
        if (user_search == array[mid]){
            return mid;
        }
        else if (user_search > array[mid]){
            return binarySearch(array, user_search, mid + 1, high);
        }
        else{
            return binarySearch(array, user_search, low, mid - 1);
        }
    }
    else
    {
        return -1;
    }
};

В приведенном выше коде мы используем рекурсивный метод для поиска. Функция бинарного поиска имеет четыре аргумента: массив, в котором мы должны выполнить поиск (массив), элемент, который мы должны найти (user_search), самый низкий индекс отправленного массива (low) и, наконец, самый высокий индекс массива (high). Когда функция вызывается из основной функции, младший индекс всегда будет равен нулю, а старший индекс будет числом, полученным после вычитания единицы из размера массива, что дает последний индекс массива.

Здесь мы с самого начала проверяем, что там, где минимум меньше или равен максимуму, это потому, что он решает, существует искомый элемент или нет. Затем мы выводим среднее из нижнего и верхнего индексов и устанавливаем базовый случай для нашей рекурсивной функции. То есть, если средний элемент искомой части массива равен искомому элементу, то мы имеем свой ответ, который и возвращаем. В противном случае делаем две проверки: больше или меньше искомый элемент среднего элемента искомой части массива; если искомый элемент больше, то мы выполняем рекурсивный вызовl, но мы меняем наш нижний индекс на средний + 1, что позволяет функции узнать, в какой части массив для продолжения поиска. Точно так же, если искомый элемент меньше, мы делаем рекурсивный вызов и меняем наш более высокий индекс на средний -1. Другими словами, изменение младшего и старшего индекса в рекурсивном позволяет нам обрезать массив и сделать его короче, чтобы мы продолжали поиск только в той части, где мы ближе к результату.

Бинарный поиск — это быстрый алгоритм поиска с временной сложностью в худшем случае O(log n). Это намного эффективнее, чем линейный поиск. Однако у алгоритма бинарного поиска есть определенные ограничения. Во-первых, мы можем использовать этот алгоритм только с отсортированными массивами. Более того, бинарный поиск не работает с массивами с повторяющимися элементами.

Удачного программирования👨‍💻