資料結構
網路
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 次瀏覽
廣告