Двоичный код поиска

Question

Я кодирую свою собственную функцию для бинарного алгоритма поиска, и я не могу найти расхождения в логике. Когда я ищу 4, он не возвращает идеальный ответ.

код ниже:

var list = [1,2,3,4,6,7,13,18,19]; 

function binarySearch(list,number) { 
    var newList = list; 
    while (newList.length >= 1) { 
     var halfNum = Math.round(newList.length/2); 
      if (newList[halfNum] === number) { 
      return "Number Found"; 
     } else if (newList[halfNum] < number) { 
      newList = newList.slice(halfNum + 1,newList.length - 1); 
     } else { 
      newList = newList.slice(0,halfNum - 1); 
     } 
    } 
} 


console.log(binarySearch(list,4)); 

Answer 1

Проблема здесь состоит в том, что вы делаете диапазоны неправильно. Код JavaScript функция ломтика разрезает массив в интервале [старт, финиш), и тем, что я имею в виду, что она не включает в себя конечный индекс в новом массиве

Таким образом, вы shoudl изменить:

} else if (newList[halfNum] < number) { 
     newList = newList.slice(halfNum + 1,newList.length - 1); 
    } else { 
     newList = newList.slice(0,halfNum - 1); 
    } 

К следующему:

} else if (newList[halfNum] < number) { 
     newList = newList.slice(halfNum + 1,newList.length); 
    } else { 
     newList = newList.slice(0,halfNum); 
    }