JS - Бинарный поиск

Question

Новичок в JS, пытался написать функцию для бинарного поиска. Принимает параметры: массив и число, если это число есть в массиве, то возвращает индекс. Но мой код зацикливается, подскажите где проблема?

let arr2 = [1,2,3,4,5]

function binarySearch(array, num){
  let low = 0;
  let high = array.length - 1;
  
  while(low <= high){
    let mid = Math.floor((low + high)/2);
    if(array[mid] === num){
      return mid;
    } else if (array[mid] < num){
       high = mid + 1;
    } else {
       low = mid - 1;
    }
  }
  return -1;
}

console.log(binarySearch(arr2, 4))

Answer 1

Похоже, что проблема в этом участке кода:

else if (array[mid] < num){
   high = mid + 1;
} else {
   low = mid - 1;
}

Если рассмотреть итерации, то для binarySearch(arr2, 4) происходит примерно следующее:

1: low=0, high=4, mid=2, array[mid]=3, array[mid]<num=true
2: low=0, high=3, mid=1, array[mid]=2, array[mid]<num=true
3: low=0, high=2, mid=1, array[mid]=2, array[mid]<num=true
4: low=0, high=2, mid=1, array[mid]=2, array[mid]<num=true
.... // и тут получается бесконечный цикл поскольку high всегда остается равен 2

Для того, чтобы это исправить, hight нужно оставлять прежним, а low устанавливать в mid + 1 при array[mid] < num. Аналогично для else блока нужно обновлять только high.

В итоге должно быть что-то вроде такого:

else if (array[mid] < num){
   low = mid + 1;
} else {
   high = mid - 1;
}

БЛОГ НА HUSL

JS - Бинарный поиск

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