首页 >后端开发 >C++ >许多二分查找实现中的一个问题?

许多二分查找实现中的一个问题?

WBOY
WBOY转载
2023-09-10 16:21:08897浏览

许多二分查找实现中的一个问题?

我们知道二分搜索算法比线性搜索算法更好。该算法执行所需的时间为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;
}

这个算法在开始和结束达到一个较大的数之前都能正常工作。如果 (开始 + 结束) 超过了 232 - 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

以上是许多二分查找实现中的一个问题?的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除