javascript - 可汗学院算法挑战 : Binary Search

Question

下面是用JS写的一个简单的二分查找代码。这段代码返回 -1 而它应该返回 20。我环顾四周后所做的事情:

1. 将“while(min < max)”替换为“while(min <= max)”会在 KhanAcademy 上弹出错误。

2. 我使用了 Math.floor 函数，由于某种原因它弹出错误“env.Math.floor 不是一个函数”，所以我改用了“Math.round”。

    var doSearch = function(array, targetValue) {
      var min = 0;
      var max = array.length - 1;
      var guess;
      while (min < max) {
        guess = Math.round((max + min) / 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);
     //print (primes[]);
     //Program.assertEqual(doSearch(primes, 73), 20);

Answer 1

我建议在分配新值时将 min rps max 值更改为 guess。

此外，我建议将 Math.round 更改为 Math.floor。

(小提示:返回后，if子句结束，所以不需要else if。)

var doSearch = function (array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    while (min < max) {
        guess = Math.floor((max + min) / 2);
        if (array[guess] === targetValue) {
            return guess;
        }
        if (array[guess] < targetValue) {
            min = guess;
        } else {
            max = guess;
        }
    }
    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],
    result = doSearch(primes, 73);

console.log("Found prime at index " + result);