Почему при вызове функции на странице, она зависает?

Question

Решил для тренировки написать функцию бинарного поиска целых чисел в массиве. Есть два массива и функция:


let arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let arr2 = [9, 8, 7, 6, 5, 4, 3, 2, 1];

let binarySerch = (arr, num) => {

    let currentIndex = arr.length / 2;

    if (arr[0] == num) return 0;

    while (arr[currentIndex] != num) {
        if (arr[currentIndex] < num) currentIndex /= 2;
        else currentIndex *= 2;
    }
    if (currentIndex == 1 && arr[0] != num) return -1;
    return currentIndex;
}

//console.log(binarySerch(arr2, 6));

Чтобы смотреть результат, использую gulp и browserSync. Почему-то при вызове функции вкладка начинает постоянно крутиться, а gulp не выполняет сборку js. В чем может быть проблема? И еще у меня есть связанный вопрос к этому алгоритму.

Answer 1

В данном случае очевиден бесконечный цикл.

В примере в вопросе в массиве нечетное количество элементов.

В этом случае let currentIndex = arr.length / 2; не целое число, а значит arr[currentIndex] будет возвращать undefined

В итоге условие в цикле всегда истинно и цикл не заканчивается.

Для решения нужно либо округлить значение, либо отбросить дробную часть.

Например с помощью метода Math.floor

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

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

Бинарный поиск может выглядеть так:

let arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let arr2 = [9, 8, 7, 6, 5, 4, 3, 2, 1];

let binarySerch = (arr, num) => {

  /* определяем концы интервала*/
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    /* проверяем значение в концах */
    if (arr[left] == num) return left;
    if (arr[right] == num) return right;

    /* выбираем опорный элемент в середине */
    let currentIndex = Math.floor((left + right) / 2);

    /* проверяем значение */
    if (arr[currentIndex] == num) return currentIndex;

    /* сдвигаем интервал */
    if (arr[currentIndex] < num) {
      left = currentIndex;
    } else {
      right = currentIndex;
    }
  }
  return -1;
}

console.log(binarySerch(arr1, 8))

Answer 2

Проблема в том, что у вас, скорее всего, создаётся бесконечный цикл.

Если ваш currentIndex равен нечетному числу, currentIndex /= 2 приведёт к созданию дробного индекса (например 2.5). Когда массив получает дробное число в качестве индекса, результатом будет undefined, т.е. мы сравниваем undefined < num, что в любом случае будет false.

Предположим, что при входе в цикл currentIndex = 5. Если после первой итерации мы поделили currentIndex на 2, в следующей итерации у нас currentIndex = 2.5. т.к. результат сравнения arr[2.5] < num будет false, мы снова повторяем предыдущий случай. Это и создаёт бесконечный цикл.

Решением будет округлять деление currentIndex /= 2 до целых чисел.

БЛОГ НА HUSL

Почему при вызове функции на странице, она зависает?

Ответы (2 шт):