多くの二分探索の実装における問題？

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

例

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つの負の数を返す場合があります。また、負の数は配列インデックスとしてサポートされていないため、問題が発生する可能性があります。

この問題を克服するには、いくつかの異なる方法があります。

方法1

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

2番目のメソッドはJavaでのみ機能します。CまたはC++には>>>演算子がないためです。

方法2（Javaのみ）

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

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

方法3

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