В своей второй статье на Medium я хочу рассказать о бинарном поиске и о том, как этот алгоритм работает на TypeScript. Я опубликовал свой фрагмент кода на Github.
Что такое бинарный поиск?
Двоичный поиск, также известный как логарифмический поиск, представляет собой алгоритм поиска, который находит положение целевого значения в структуре данных (например, в массиве). Для этого структура данных должна быть отсортирована. Невозможно использовать алгоритм бинарного поиска в несортированной структуре данных.
Временная сложность
Худший случай: O(log n)
Средний случай: O(log n)
Лучший случай: O(1)
Функция TypeScript
Как видите, сам метод не так уж и сложен. Но позвольте мне объяснить, что произойдет, на примере.
Эта функция binarySearch принимает два аргумента: массив целых чисел и целое число.
числа: [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
цель: 2
Это означает, что мы хотим найти индекс того массива (NUMS), в котором элемент содержит целое число 2 (TARGET).
При линейном поиске мы перебираем этот массив, скорее всего, начиная с индекса 0, пока не найдем нужный элемент. При бинарном поиске мы многократно делим интервал поиска пополам. Для этого мы следуем этому потоку:
- Сравните TARGET со средним элементом.
- Если TARGET совпадает со средним элементом, мы возвращаем средний индекс.
- В противном случае, если TARGET больше среднего элемента, то TARGET может лежать только в правой половине подмассива после среднего элемента. Итак, мы повторяемся для правой половины.
- В противном случае (ЦЕЛЬ меньше) повторяется для левой половины.
Если вы хотите узнать больше об этом алгоритме поиска, я могу порекомендовать вам видео с сайта HackerRank.
Спасибо, что прочитали мою вторую статью на Medium. Надеюсь, я смог освежить ваши знания.
В очередной раз выложил свой код на Github.
Ваше здоровье!
Надеюсь, вам понравилось это читать. Если вы хотите поддержать меня как писателя, рассмотрите возможность подписки стать участником Medium. Всего 5 долларов в месяц, и вы получаете неограниченный доступ к Medium.
Хотите поддержать меня? Купи мне кофе.
Читать дальше
Создавайте компонуемые веб-приложения
Не создавайте веб-монолиты. Используйте Bit для создания и компоновки несвязанных программных компонентов — в ваших любимых фреймворках, таких как React или Node. Создавайте масштабируемые и модульные приложения с мощными и приятными возможностями разработки.
Перенесите свою команду в Bit Cloud, чтобы совместно размещать и совместно работать над компонентами, а также значительно ускорить, масштабировать и стандартизировать разработку в команде. Начните с компонуемых интерфейсов, таких как Design System или Micro Frontends, или исследуйте компонуемый сервер. Попробуйте →
