如何實現二進制搜索在JavaScript

https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/p/challenge-binary-search 如何實現二進制搜索在JavaScript

我下面的僞代碼來實現鏈接算法，但不知道什麼是錯我的代碼。

這裏是我的代碼：

/* Returns either the index of the location in the array, 
    or -1 if the array did not contain the targetValue */ 

    var doSearch = function(array, targetValue) { 
    var min = 0; 
    var max = array.length - 1; 
    var guess; 

    while(min < max) { 
     guess = (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, 2); 
println("Found prime at index " + result); 

//Program.assertEqual(doSearch(primes, 73), 20);

來源

2015-04-06 Begginer

'while'後面，檢查'array [min] == target'或'array [max] = target'。 – 2015-04-06 08:56:14

'println（）'不是Javascript中的函數。我想你想'console.log（）'：https：//developer.mozilla.org/en-US/docs/Web/API/Console/log – 2015-04-06 09:06:18

爲了得到你需要指定像array[1]整數數組的值。 array[1.25]將在您的情況下返回undefined。

爲了讓它正常工作，我只是在你的循環中加入了Math.floor以確保我們得到一個整數。

編輯：作爲@KarelG pointet你還需要在你的while循環中添加<=。這適用於min和max已變成相同的情況，在這種情況下guess === max === min。沒有<=循環將不會在這些情況下運行，並且該函數將返回-1。

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; 
     } 
     else if (array[guess] < targetValue) { 
      min = guess + 1; 
     } 
     else { 
      max = guess - 1; 
     } 

    } 

    return -1; 
}

你可以使用任何一種Math.floor，Math.ceil和Math.round。

我希望這是一個小小的幫助，我不是很擅長解釋，但我會盡我所能來詳細說明。

來源

2015-04-06 09:00:50

'<='需要while循環。嘗試通過搜索11的代碼。 – KarelG 2015-04-06 09:06:10

@ KarelG哦對，謝謝！ – 2015-04-06 09:08:30

爲什麼不Math.round。請解釋？ – Begginer 2015-04-06 09:47:51

在你的代碼的時候分鐘等於最大值則循環結束。但是，在這種情況下，你不檢查是否array[min] == targetValue

因此改變代碼，這將最有可能解決您的問題

/* Returns either the index of the location in the array, 
    or -1 if the array did not contain the targetValue */ 

    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; 
     } 
     else if (array[guess] < targetValue) { 
      min = guess + 1; 
     } 
     else { 
      max = guess - 1; 
     } 

    } 

    return -1; 
};

的jsfiddle鏈接：http://jsfiddle.net/7zfph6ks/

希望它能幫助。

PS： 在代碼中唯一的變化是這一行：while (min <= max)

來源

2015-04-06 08:56:00 Diptendu

有人可以解釋downvote和爲什麼這個評論應該刪除？ – Diptendu 2015-04-06 09:03:25

我沒有downvoted但是，請自己嘗試代碼。我懷疑它不起作用。 – KarelG 2015-04-06 09:04:20

如果有人還在尋找答案，你需要使它（最大值> =分鐘）

while (max >= min) { 
guess = Math.floor((max + min)/2); 
if (array[guess] === targetValue) { 
    return guess; 
} 
else if (array[guess] < targetValue) { 
    min = guess + 1; 
} 
else { 
    max = guess - 1; 
    } 
} 
return -1;

來源

2015-06-29 14:45:42

你只需要取消對Program.assertEqual 這樣的：

Program.assertEqual(doSearch(primes, 73), 20);

不是這樣的：

//Program.assertEqual(doSearch(primes, 73), 20);

來源

2015-08-27 13:57:46

如何實現二進制搜索在JavaScript

回答

相關問題