Бинарный поиск на JavaScript

Введение

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

Алгоритм бинарного поиска

Для начала практики в программировании откройте Терминал/SSH и введите node. Алгоритм бинарного поиска используется для нахождения индекса заданного элемента в отсортированном массиве. Вот шаги по реализации алгоритма бинарного поиска:

1. Объявите левые и правые границы поиска, l и r, инициализированные соответственно значениями 0 и длиной массива.
2. Используйте цикл while, чтобы последовательно сужать подмассив поиска, деля его пополам с использованием Math.floor().
3. Если элемент найден, верните его индекс. В противном случае верните -1.
4. Обратите внимание, что этот алгоритм не учитывает дублирующиеся значения в массиве.

Вот пример реализации алгоритма бинарного поиска на JavaScript:

const binarySearch = (arr, item) => {
  let l = 0,
    r = arr.length - 1;
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    const guess = arr[mid];
    if (guess === item) return mid;
    if (guess > item) r = mid - 1;
    else l = mid + 1;
  }
  return -1;
};

Вы можете протестировать функцию binarySearch с помощью следующих примеров:

binarySearch([1, 2, 3, 4, 5], 1); // 0
binarySearch([1, 2, 3, 4, 5], 5); // 4
binarySearch([1, 2, 3, 4, 5], 6); // -1

Резюме

Поздравляем! Вы завершили лабу по бинарному поиску. Вы можете практиковаться в более лабах в LabEx, чтобы улучшить свои навыки.