このバイナリ検索の実装は、常に正しく動作しますか？

Question

以下に示すように、整数の配列を2進数でスカラーで検索するコードを記述しました。私は、バイナリ検索は実装するのが非常に難しいことを知っています。だから、私はこのコードが常に正しく動作するかどうかを知りたい。私はテスト配列に対してテストすることで試してみたところ、うまくいきました。しかし、いつもうまくいくかどうかは分かりません。

メモ：アレイのサイズは、最大整数値の半分以下であるとします。あなたの仮定の下で

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)/2の代わりにval guess = starti + (endi - starti)/2と書くことをお勧めします。なぜなら、後者は一般的なケースでオーバーフローする可能性があるからです。

return binarySearch(arr, starti, guess-2, x)の代わりにreturn binarySearch(arr, starti, guess-1, 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) 
    } 
} 

注意しきい値は単にランダムな推測ことと性能測定を行うことによって決定しなければなりません。