Поиск: линейный и двоичный

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

Ищем одно значение

Задача поиска состоит в том, чтобы найти, где значение лежит в наборе данных, или узнать, что его там нет. Телефон делает это, когда ты набираешь имя контакта, магазин делает это, когда проверяет, есть ли товар на складе, а проверка орфографии делает это для каждого набранного слова. На входе список и искомое значение. На выходе позиция искомого значения или знак вроде -1, который значит «не найдено».

Линейный поиск: по одному

Самый простой способ: начать слева и проверять значения по очереди, пока не найдёшь искомое или не кончится список. Это линейный поиск. Он работает на любом списке, отсортированном или нет. Его стоимость зависит от удачи: если искомое значение первое, хватит одной проверки; если оно последнее или его нет, проверишь каждое значение. Для списка из n значений в худшем случае нужно n проверок. Вдвое более длинному списку может понадобиться вдвое больше проверок, отсюда и название «линейный»: работа растёт по прямой вместе с размером.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // нашли
  }
  return -1;                             // проверили всё
}

Двоичный поиск: дели остаток пополам

Если список отсортирован, можно действовать гораздо лучше. Вспомни игру «угадай число»: кто-то загадывает число от 1 до 100 и отвечает только «больше» или «меньше». Разумный игрок сначала называет 50. Каков бы ни был ответ, половина вариантов отпадает. Следующая попытка берёт середину того, что осталось, и так далее. Двоичный поиск делает ровно это с отсортированным списком. Он держит две границы, lo и hi, вокруг части, где искомое значение ещё может быть. Он проверяет среднее значение. Если это искомое, работа закончена. Если среднее значение меньше искомого, то и всё слева от него меньше, поэтому lo переходит за середину. Если больше, hi переходит перед серединой. Когда lo заходит за hi, ничего не осталось, и искомого значения в списке нет.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // искомое справа
    else hi = mid - 1;                     // искомое слева
  }
  return -1;
}

Сколько проверок?

Каждая проверка двоичного поиска как минимум вдвое уменьшает оставшуюся часть. Если начать с n значений, после одной проверки останется не больше примерно n/2, после двух примерно n/4, и так далее, пока не останется одно значение. Число делений пополам, нужных, чтобы дойти от n до 1, равно двоичному логарифму n, его записывают log₂ n. Если учесть и последнюю проверку, двоичному поиску нужно не больше ⌊log₂ n⌋ + 1 проверок, где ⌊ ⌋ означает округление вниз. Для 100 значений это 7 проверок, поэтому в «угадай число» всегда можно выиграть за 7 попыток. Для 1000 значений это 10, для миллиона 20, а для миллиарда 30.

Подвох: список должен быть отсортирован

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