Алгоритмы и структуры данных — самая важная тема для программиста, стремящегося заработать большие деньги.

Бинарный поиск — популярный поисковый алгоритм. Он очень производительный. Он оценивает временную сложность O (log2N).

Вот несколько случаев, когда вы найдете людей, использующих бинарный поиск:

  • Поиск песни в отсортированном списке песен
  • Нахождение слова в словаре
  • Двоичный поиск используется на большинстве языков за кулисами.

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

Как это работает?

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

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

В программировании мы продолжаем это делать, пока не получим одну страницу со словом «Кот» или False для не найдено.

Пример в коде

Мы реализуем точно такой же метод Binary Search вместо того, чтобы искать «Cat» в словаре, мы ищем значение в отсортированном массиве чисел. Чтобы добавить, вы можете использовать это с любой отсортированной структурой данных, где у вас есть среднее значение или медиана.

function binarySearch(sortedArray, key) {
   const middleIndex = Math.floor(sortedArray.length/2)
   const middleEl = sortedArray[middleIndex]
   // We need the sortedArray.length > 1 because that’ll stop our process when we have only 1 element.
   if (middleEl === key) return true
   else if (key <= middleEl && sortedArray.length > 1) {
      return binarySearch(sortedArray.splice(0, middleIndex), key)
   } else if (key > middleEl && sortedArray.length > 1) {
    return binarySearch(sortedArray.splice(middleIndex,    sortedArray.length ), key)
   } else {
   return false
   } 
}
binarySearch([5, 7, 12, 16, 36, 39, 42, 56, 71], 56);

Вы сделали это!

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