如何在分而治之的二進制搜索中找到數字的索引？

Question

我可以使用分而治之的二進制搜索找到我想要的號碼，但我怎麼能找到原始數組中的個數指標，而無需使用for循環和的indexOf？

function search(array, value) { 

    var midpoint = Math.floor(array.length/2) 

    if (value > array[midpoint]) { 
     var slicedArray = array.slice(midpoint) 
    } else { 
     var slicedArray = array.slice(0,midpoint) 
    } 
    return slicedArray[Math.floor((slicedArray.length/2))] === value ? value : search(slicedArray, value) 
} 

console.log(search([1,3,16,22,31,33,34], 34)) 

Answer 1

您可以也應該大幅壓縮此代碼，但爲了更好地說明概念，我已經將它留在更長的形式中。

function search(array, value) { 
    if (array.length == 0) 
     return NaN; 

    var midpoint = Math.floor(array.length/2); 

    if (array[midpoint] === value) 
     return midpoint; 

    if (array[midpoint] < value) 
     return search(array.slice(midpoint+1),value) + midpoint + 1; 

    if (array[midpoint] > value) 
     return search(array.slice(0,midpoint),value); 
} 

當你寫一個遞歸函數，前兩個問題你應該總是問自己是「我怎麼知道我做了什麼？」和「沒有，真的沒有辦法達到完成條件嗎？」

你要確保已經覆蓋每一種可能的狀態。在這種情況下，有四種：

• 該數組爲空。
• 數組中點的值等於您的搜索值。
• 在陣列的中點值小於搜索值。
• 數組中點處的值大於您的搜索值。

使用NaN作爲'搜索失敗'的返回值是很方便的，因爲它避免了需要空值檢查條件邏輯繞遞歸值返回鏈; NaN加上一個數字等於NaN。

你不需要知道，不應該嘗試計算你發現它的那一刻，幾個遞歸調用後，原始數組中搜索值的指數。調用實例的工作是將它所知道的（它自己的中點）與遞歸結果相結合，並返回一個有用的值來備份鏈。事實上，沒有特定的函數調用應該「知道」它是原始調用還是遞歸。如果你發現自己需要知道這個問題的答案，這是一個警告標誌，你應該重新檢查你的邏輯。

Answer 2

你可以有一個包裝函數_binarySearch做實際的二進制搜索，與服用兩個附加參數l, r一起，而你可以調用只有兩個參數array, value

function _binarySearch(array, value, l, r) { 
if (l > r) return -1; 

var midPoint = Math.floor((l + r)/2); 

if (value == array[midPoint]) 
    return midPoint; 

else if (value > array[midPoint]) 
    return _binarySearch(array, value, midPoint + 1, r); 

else 
    return _binarySearch(array, value, l, midPoint - 1); 
} 

function search(array, value) { 
    return _binarySearch(array, value, 0, array.length); 
} 

搜索如果你想知道第一齣現一個元素，該算法的最壞情況時間複雜度不再是O（log n）了，它退化爲O（n）。

這一修改必要

if (value == array[midPoint]) { 
    while(midPoint > -1 && array[midPoint] == value) 
     --midPoint; 

    return midPoint + 1; 
}