Searching

Я работаю над изучением структур данных и алгоритмов. Один алгоритм, который очень хорошо работает для улучшения временной сложности Big O, - это двоичный поиск, который улучшает базовый линейный поиск. Однако, чтобы использовать двоичный поиск, элементы, которые вы ищете, должны быть отсортированы.

Я начну с демонстрации линейного поиска и того, как он работает и как двоичный поиск улучшает его. Принцип работы линейного поиска заключается в том, что он просматривает каждый элемент и проверяет, соответствует ли он искомому элементу. Я дам код для линейного поиска (в JavaScript), и для этого примера код получит массив и значение элемента, который мы ищем:

function linearSearch(arr, val){
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === val){
            return i
        }
    }
    return -1
}

Если мы находим искомое значение, мы возвращаем индекс этого значения в массиве, в противном случае мы возвращаем -1, что означает, что мы не смогли найти значение в массиве. Это может быть эффективным в лучшем случае: мы находим наше значение в первом элементе массива и возвращаем 0 (для индекса 0), но мы можем рассчитывать на то, что сразу найдем то, что ищем, или найдем значение вообще. . Итак, для нашего худшего случая, а также для среднего линейного поиска, мы получаем Big O из O (n), когда он проходит через каждое значение массива.

Двоичный поиск

Как я уже упоминал ранее, для использования двоичного поиска элементы должны быть отсортированы. Но учитывая, что элементы отсортированы, мы можем гораздо эффективнее использовать функцию поиска. Бинарный поиск работает с использованием указателя для начальной, конечной и средней точки (также может быть левой, правой и средней). Поиск начинается с просмотра среднего значения, если среднее значение - это то, что мы ищем, тогда все готово. В противном случае мы увидим, больше или меньше искомое значение среднего значения. Если значение, которое мы ищем, больше среднего значения, мы игнорируем среднее значение и все, что ниже него. Тогда новая начальная точка становится значением после среднего значения, а новое среднее значение - серединой между новой начальной точкой и конечной точкой. Точно так же, если значение, которое мы ищем, меньше среднего значения, мы поступим наоборот. Что означало бы игнорировать среднее значение и все, что выше него. Затем новая конечная точка становится значением перед средним значением, а новое среднее значение становится серединой между начальной точкой и новой конечной точкой. Этот процесс повторяется до тех пор, пока либо элемент не будет найден, либо мы не определим, что то, что мы ищем, не существует в массиве.

function binarySearch(arr, val){
    let left = 0
    let right = arr.length - 1
    let middle = Math.floor((right + left)/2)
    
    while(arr[middle] !== val && left <= right){
        if(val < arr[middle]){
            right = middle - 1
        } else {
            left = middle + 1
        }
        middle = Math.floor((right + left)/2)
    }
    if(arr[middle] === val){
        return middle
    }
    return -1
}

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

Курсы Udemy Мастер-класс по алгоритмам JavaScript и структурам данных и Освойте собеседование по кодированию: структуры данных + алгоритмы помогли мне изучить алгоритмы поиска и проработать их.