我的二進制搜索實現能夠正常工作嗎？

Question

我已經編寫了用於在scala中搜索整數數組的二進制代碼，如下所示。我知道二分查找實施起來相當棘手。所以，我想知道這個代碼是否總能正常工作。我已經通過對測試數組進行測試來嘗試它，並且它可以工作。但是，我不確定它是否會始終有效。

NOTE：假設數組大小永遠不會超過最大整數值的一半。

def binarySearch(arr: Array[Int], starti: Int, endi: Int, x: Int) : Int = 
{ 
    if (starti > endi) 
     return -1 

    val guess = (starti + endi)/2 

    if (arr(guess) == x) 
     return guess 

    if ((guess != 0) && (arr(guess-1) == x)) 
     return guess - 1 

    if ((guess != endi) && (arr(guess+1) == x)) 
     return guess + 1 

    if (arr(guess) > x) 
     return binarySearch(arr, starti, guess-1, x) 
    else 
     return binarySearch(arr, guess+1, endi, x) 
} 

Answer 1

在你的假設它似乎是正確的。不過，我總是建議編寫val guess = starti + (endi - starti)/2而不是val guess = (starti + endi)/2，因爲後者在一般情況下可能會溢出（但不是在您的假設下）。

此外，搜索鄰居是相當罕見的，在你的情況下，它只是開銷，因爲您使用return binarySearch(arr, starti, guess-1, x)代替return binarySearch(arr, starti, guess-2, x)，類似的還有return binarySearch(arr, guess+1, endi, x)，忽略你已經檢查了這些。

我建議刪除guess的鄰居測試。相反，計算間隔的大小（endi - starti），如果它小於某個閾值，則線性搜索數組x（由於緩存的工作原理，線性遍歷速度相當快）。如果它更大，則使用遞歸二進制搜索。請注意，在下面的示例中，我稍微更改了界面：給定搜索間隔不包括endi以使初始呼叫更加舒適（binarySearch(arr, 0, arr.length, x)）。

def binarySearch(arr: Array[Int], starti: Int, endi: Int, x: Int) : Int = 
{ 
    val threshold = 100 

    val len = endi - starti 
    if (len <= 0) { 
     return -1 
    } 

    // Optional and purely for performance reasons 
    if (len < threshold) { 
     for (i <- starti until endi) { 
      if (arr(i) == x) { 
       return i 
      } 
     } 
    } 


    val guess = starti + len/2 
    if (arr(guess) == x) { 
     return guess 
    } else if (arr(guess) > x) { 
     return binarySearch(arr, starti, guess, x) 
    } else { 
     return binarySearch(arr, guess + 1, endi, x) 
    } 
} 

請注意，閾值只是隨機猜測，必須通過性能測量來確定。