在JavaScript中執行二進制搜索

Question

請我發現這個代碼實現了二分查找，但是當我嘗試改變其中的某些內容時，我得到的結果並不是我期望的。下面的代碼：

function binary_search(list, lo, hi, key){ 
var mid; 

if (lo > hi) 
{ 
    console.log("Key not found\n"); 
    return; 
} 
mid = Math.floor((lo + hi)/2); 
if (list[mid] == key) 
{ 
    console.log("Key found\n"); 
    //return mid; Expected this to return the index where the key was found 
    //but it returns undefined... 
} 
else if (list[mid] > key) 
{ 
    binary_search(list, lo, mid - 1, key); 
} 
else if (list[mid] < key) 
{ 
    binary_search(list, mid + 1, hi, key); 
} 
} 

binary_search([1,3,5,6,7,9],0,5,1)// logs 'Key found' to the console(working correctly); 

當我試圖在代碼中改變了一些東西（在上面的代碼中的註釋部分顯示），我得到了意想不到的結果，但我不知道爲什麼。再次檢查if (lo > hi)需要什麼，因爲我認爲hi應該總是比lo更高。 hi是否會低於lo？有人可以讓我清楚這些事嗎？

Answer 1

試試這個 -

function binarySearch(arr, num, l, r){ 
 
\t if(arr instanceof Array){ 
 
    \t 
 
    l = isNaN(l) ? 0 : l; 
 
    r = isNaN(r) ? arr.length - 1: r; 
 
    let mid = l + 1 + Math.round((r - l)/2 - 1);  
 
    console.log(l, r, mid, arr[mid]); 
 
    
 
    if(num == arr[mid]){ 
 
    \t console.log("found"); 
 
     return mid; 
 
    } 
 
    
 
    if(typeof arr[mid] == "undefined" || l == r){ 
 
    \t console.log("not found"); return -1; 
 
    } 
 
    
 
    if(num < arr[mid]){ 
 
    \t console.log("take left"); 
 
     return binarySearch(arr, num, l, r - mid); 
 
    } 
 
    
 
    console.log("take right"); 
 
    return binarySearch(arr, num, mid, r); 
 
    
 
    } 
 
} 
 

 
console.log(binarySearch([0, 0, 1 ,1, 2, 3, 5, 6, 11], 2));