javascriptでバイナリ検索を実装する

Question

JavaScriptでバイナリ検索を実装しようとしています。私は自分のスクリプトで何がうまくいかないのか分からない。検索ボタンをクリックすると、ページが反応しなくなります。事前に感謝しています。

var i,print,arr; 
 
\t arr = [1,2,3,4,5,6,7,8,9,10]; 
 
\t print = document.getElementById("showArray"); 
 
\t for(i = 0; i < arr.length; i++){ 
 
\t print.innerHTML += arr[i] + "&nbsp;"; 
 
\t } 
 
\t function binarySearch(searchValue){ 
 
\t var lowerIndex, higherIndex, middleIndex,writeResult; 
 
\t lowerIndex = 0; 
 
\t higherIndex = arr.length; 
 
\t writeResult = document.getElementById("showResult"); 
 
\t while(lowerIndex <= higherIndex){ 
 
\t  middleIndex = (higherIndex + lowerIndex)/2; 
 
\t \t if(searchValue == arr[middleIndex]){ 
 
\t \t writeResult.innerHTML = "PRESENT"; 
 
\t \t consol.log('Present'); 
 
\t \t break; 
 
\t \t } 
 
\t \t else if(searchValue > arr[middleIndex]){ 
 
\t \t lowerIndex = middleIndex + 1; 
 
\t \t } 
 
\t \t else if(searchValue < arr[middleIndex]){ 
 
\t \t higherIndex = middleIndex - 1; 
 
\t \t } 
 
\t } 
 
\t }

<button onclick = "binarySearch(1)">SEARCH</button> 
 
\t <p id = "showArray" style = "font-size: 40px; padding:0px;">  </p> 
 
\t <p id = "showResult">Result is:</p>

Answer 1

は

Array.prototype.br_search = function (target) 
{ 
    var half = parseInt(this.length/2); 
    if (target === this[half]) 
    { 
    return half; 
    } 
    if (target > this[half]) 
    { 
    return half + this.slice(half,this.length).br_search(target); 
    } 
    else 
    { 
    return this.slice(0, half).br_search(target); 
    } 
}; 

l= [0,1,2,3,4,5,6]; 

console.log(l.br_search(5)); 

Answer 2

主な問題のようなものを試してみてください、あなたが持っているmiddleIndexのための計算の整数部分を使用することではありません。これは、インデックスが整数でなければならないため、配列の特定のインデックスで値をチェックすることは不可能です。

var i, 
 
    print = document.getElementById("showArray"), 
 
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; 
 

 
for (i = 0; i < arr.length; i++) { 
 
    print.innerHTML += arr[i] + "&nbsp;"; 
 
} 
 

 
function binarySearch(searchValue) { 
 
    var lowerIndex = 0, 
 
     higherIndex = arr.length - 1, 
 
     middleIndex, 
 
     writeResult = document.getElementById("showResult"); 
 

 
    while (lowerIndex <= higherIndex) { 
 
     middleIndex = Math.floor((higherIndex + lowerIndex)/2); 
 
     if (searchValue == arr[middleIndex]) { 
 
      writeResult.innerHTML = "PRESENT " + middleIndex; 
 
      break; 
 
     } 
 
     if (searchValue > arr[middleIndex]) { 
 
      lowerIndex = middleIndex + 1; 
 
     } else { 
 
      higherIndex = middleIndex - 1; 
 
     } 
 
    } 
 
}

<button onclick="binarySearch(2)">SEARCH</button> 
 
<p id="showArray" style="font-size: 40px; padding:0px;">  </p> 
 
<p id="showResult">Result is:</p>

Answer 3

breakずに二分探索の反復例。

実行時間：おそらくlog2(n)

function search(array, target) { 
 
    let min = array[0] 
 
    let max = array.length - 1; 
 
    let guess; 
 
    
 
    while (max >= min) { 
 
    guess = Math.floor((min+max)/2); 
 
    if (array[guess] === target) { 
 
     return guess; 
 
    } else if (array[guess] > target) { 
 
     max = guess - 1; 
 
    } else { 
 
     min = guess + 1; 
 
    } 
 
    } 
 

 
    return -1; 
 
} 
 

 
const 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]; 
 
console.log(search(primes, 67));