获得二进制搜索的迭代次数

Question

我正在尝试实现一个二进制搜索功能，该功能返回元素的索引以及获取元素所需的迭代次数。

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}。

Answer 1

您将获得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));