为什么我的算法无法在我的数组中找到索引？

Question

为什么我的算法 returning “-1”意味着目标值 73 不在数组中？（当数组中显然有 73 时）。 [这是来自可汗学院，但没有帮助]

它应该 return 数组中位置的索引，如果数组不包含目标值

，则为“-1”

Var doSearch = function(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    while(max >= min) {
        guess = floor((max*1 + min*1) / 2);
        if (guess === targetValue) {
            return guess;
        } else if (guess < targetValue) {
            min = guess + 1;
        } else {
            max = guess - 1;
        }
    }
    return -1;
};

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

var result = doSearch(primes, 73);
println("Found prime at index " + result);

Answer 1

您将 guess 设置为数组索引，但随后您将其与 targetValue 进行比较。您需要比较该索引处的数组元素。

var doSearch = function(array, targetValue) {
  var min = 0;
  var max = array.length - 1;
  var guess;
  var guessvalue;
  while (max >= min) {
    guess = Math.floor((max * 1 + min * 1) / 2);
    guessValue = array[guess];
    if (guessValue === targetValue) {
      return guess;
    } else if (guessValue < targetValue) {
      min = guess + 1;
    } else {
      max = guess - 1;
    }
  }
  return -1;
};

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
  41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
];

var result = doSearch(primes, 73);
console.log("Found prime at index " + result);

Answer 2

您的函数 doSearch() 不会将 array 的任何值与 targetValue 进行比较。您需要访问 guess 位置并进行比较，如下所示：

var doSearch = function(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    while(max >= min){
        guess = Math.floor((max*1 + min*1) / 2);
        if (array[guess] === targetValue) {
            return guess;
        } else if (array[guess] < targetValue) {
            min = guess + 1;
        } else {
            max = guess - 1;
        }
    }
    return -1;
};

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

var result = doSearch(primes, 73);
console.log("Found prime at index " + result);

Warning: The function floor() doesn't exist in JavaScript. You should use Math.floor(). Also, the function println(). Use console.log() instead.

为什么我的算法无法在我的数组中找到索引？

Why can't my algorithm find the index in my array?

javascript

binary-search

khan-academy