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

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

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

Там необходим начальный индекс и конечный индекс, чтобы найти средний индекс или среднюю точку.

Начало равно 0, первый индекс в массиве.

Конец равен последнему индексу в массиве или длине минус один.

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

Внутри цикла мы установим середину на полпути между началом и концом.

Мы можем написать условное выражение, чтобы проверить, соответствует ли элемент искомому значению.

Если найденное значение слишком велико, мы должны посмотреть влево от средней точки и отбросить правую половину элементов массива.

Поэтому устанавливаем конец в середину.

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

И мы продолжаем идти.

Пример того, как это может выглядеть в JavaScript:

let start = 0;
let end = array.length-1;
while(start < end){
    let middle = Math.floor(left + ((right-left)/2))
    // I am rounding down so that we are sure to get an integer
    if(array[middle] === a){
        return middle
    }else if(array[middle] < a){
        end = middle
    }else if(array[middle] > a){
        start = middle
    }
}
return "not found"
//if start is now equal to end then the item we are searching for is not in the array