数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究许多二分搜索实现中的一个问题？
众所周知，二分搜索算法优于线性搜索算法。此算法执行需要花费 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;
}此算法的运行效果良好，直到开始和结束达到一个大数字。如果 (start + end) 超过 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
更新于： 2019 年 7 月 30 日
72 次浏览
广告