多くの二分探索実装に問題がありますか?

二分探索アルゴリズムは線形探索アルゴリズムよりも優れていることがわかっています。このアルゴリズムの実行に必要な時間は O(log n) です。ただし、ほとんどの場合、実装されたコードにはいくつかの問題があります。以下に示すような二分探索アルゴリズム関数を考えてみましょう。-

Example

int binarySearch(int array[], int start, int end, int key){
   if(start <= end){
      int mid = (start + end) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

このアルゴリズムは、最初と最後で大きな数に達するまでは正常に機能します。 (開始終了) が値 2³² - 1 を超える場合、ラップ後に負の数が返される可能性があります。負の数値は配列インデックスとしてサポートされていないため、問題が発生する可能性があります。

この問題を解決するには、いくつかの方法があります。

方法 1

int mid = start + ((end - start) / 2)

C または C++ には >>> 演算子がないため、2 番目の方法は Java でのみ機能します。

方法 2 (Java のみ)

int mid = (start + end) >>> 1

C または C++ は >>> をサポートしていないため、次の方法を使用できます。

方法 3

int mid = ((unsigned int) low + (unsigned int) high) >> 1

以上が多くの二分探索実装に問題がありますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。