Получить номер итерации в бинарном поиске - PullRequest
Новая
       17

Получить номер итерации в бинарном поиске

0 голосов
/ 14 октября 2019

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

function binarySearch(array, number) {
    var obj = {}, index, count = 0;
    var start = 0;
    var end = array.length - 1;
    var middle = Math.floor((start + end) / 2);

    while(array[middle] !== number && start <= end) {
        if(number < array[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }

    array[middle] === number ? obj.index = middle : obj.index = -1;
    obj.count++
    return obj;
}

Я ожидал вывода [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22], 3,быть obj = {index:2, count:3} но получаю obj ={index;2, count:NaN}.

1 Ответ

0 голосов
/ 14 октября 2019

Вы получаете count: NaN, потому что вы никогда не инициализировали obj.count. Добавление 1 к неопределенному значению приводит к NaN.

Вам необходимо увеличить count в цикле. Затем в конце вы можете назначить obj.count = count;

И если вы собираетесь использовать троичное выражение, сделайте это в источнике назначения, а не повторяйте назначение в каждом условии. 

function binarySearch(array, number) {
  var obj = {},
    index, count = 0;
  var start = 0;
  var end = array.length - 1;
  var middle = Math.floor((start + end) / 2);

  while (array[middle] !== number && start <= end) {
    if (number < array[middle]) end = middle - 1;
    else start = middle + 1;
    middle = Math.floor((start + end) / 2);
    count++;
  }

  obj.index = array[middle] === number ? middle : -1;
  obj.count = count;
  return obj;
}

console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22], 3));
...