Функция не выходит из цикла

Question

Бинарный поиск не выходит из цикла. Код, в котором возникает проблема:

let mass=[1, 2, 3, 4, 5, 6]

function binarySearch(array, a ){

    let low=0
    let high= array.length-1

    while(low<=high){
        let mid=(low+high)/2   
        if(a===array[mid]){
            return mid
        }
        else if(a<array[mid]){
            high=mid-1
        }
        else if(a>array[mid]){
            low= mid+1
        }
    }
    return -1
}
console.log(binarySearch(mass,3))

Answer 1

проблема в том, для mid нужно брать целое число, в то время как, при делении на два может получиться дробное.

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

Отбросить дробную часть можно, например, с помощью метода Math.trunc

let mass = [1, 2, 3, 4, 5, 6]

function binarySearch(array, a) {

  let low = 0
  let high = array.length - 1
  while (low <= high) {
    let mid = Math.trunc((low + high) / 2);
    if (a === array[mid]) {
      return mid
    } else if (a < array[mid]) {
      high = mid - 1

    } else if (a > array[mid]) {
      low = mid + 1
    }
  }
  return -1
}
console.log(binarySearch(mass, 3))

БЛОГ НА HUSL

Функция не выходит из цикла

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