Алгоритмы и структуры данных — самая важная тема для программиста, стремящегося заработать большие деньги.
Бинарный поиск — популярный поисковый алгоритм. Он очень производительный. Он оценивает временную сложность 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);
Вы сделали это!
Вы понимаете бинарный поиск, и эта концепция будет использоваться во всем коде, который вы пишете. Когда вы сталкиваетесь с бинарным поиском, а это большая вероятность, потому что вы разработчик, вы можете его использовать. На следующем собеседовании вы получите работу.