许多二进制搜索实现中存在问题吗？

我们知道二进制搜索算法比线性搜索算法更好。该算法需要O（log n）的时间来执行。尽管在大多数情况下，已实现的代码仍存在一些问题。让我们考虑一个如下的二进制搜索算法函数-

示例

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)

第二种方法仅在Java中有效，因为C或C ++没有>>>运算符。

方法2（仅Java）

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

由于C或C ++不支持>>>，因此我们可以使用以下方法。

方法3

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