Khan Academyアルゴリズムの課題：バイナリ検索

Question

以下は、JSで書かれた単純なバイナリ検索コードです。このコードは戻っている-1、それは私が少し周りを見た後に行われている20物事返すべきであるのに対し、「しばらく（<最大分）」ポップだろう「（< =最大分）しばらく」に置き換え

1. をKhanAcademyでエラーを起こす。

2. 私はいくつかの理由でエラーので、代わりに「恐らくMath.roundを」使用「ENV .Math.floorは関数ではありません」ポップMath.floor機能を、使用しています。

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

私は新しい値の割り当てでguessにmin RPS max値を変更することをお勧めします。

さらに、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);

Answer 2

それは、最小値と最大値の計算であります。 "+"と " - "信号は逆になります。

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 3

あなたのコード内のほんの少しの誤差があります。はい1.

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);