java二分搜索算法常見使用誤區是什么

這篇文章主要講解了“java二分搜索算法常見使用誤區是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“java二分搜索算法常見使用誤區是什么”吧！

直接使用二分搜索法，搜索一個無序的數組或集合。
 
如果你運氣好的話，可能會搜索到你想要的數據，但是大部分情況下你不能得到你想要的結果。因為二分搜索是按照中間值來計算你要搜索數據的范圍，每次逐漸縮小范圍。如果你的結果不在一個按照升序排列的數組中，你要搜索的數據很可能被遺棄，然后返回負值。我們可以通過如下所示一段程序來斷言，數組是否是有序的。
 
for(int i=0; i< arr.length; i++) {
    if(arr[i]>arr[i+1]) {
        return 0
    }
    return 1;
}
 

自己寫了一個二分搜索算法，陷入了一個死循環，不知道為什么？


 因為你的邊界沒有完全控制好，所以造成了這種情況。如下:


反面教材 1：
數組 `int arr[] = {12,14,143,145,643,23453,233452};`
搜索數據 233452（直接陷入死循環）

int start = 0;
int end = arr.length-1;
while(start <= end) {
    int mid = (start + end) / 2;
    if(key < arr[mid]){
        end = mid;
    }else if(key > arr[mid]) {
        start = mid;
    }else {
        return mid;
    }
}
return -1;

如上這種寫法看起貌似是正確的，如果仔細分析的話，會發現數組的長度為7

* 第一次循環中間量mid=3

* 第二次循環中間量mid=4

* 第三次循環中間量mid=5

* 第四次循環中間量mid=6

* 第五次循環中間量mid=6

* 第六次循環中間量mid=6

* 第七次循環中間量mid=6
* .....
* 由此陷入死循環

反面教材 2：
如果我們通過調試之后，把程序調整成如下，循環搜索結果，發現依然是個死循環。最終卡在了中間值5上，究其原因是因為，我們的中間值不能一直縮小，所以最終導致這個問題。

int start = 0;
int end = arr.length-1;
while(start <= end) {
    int mid = (start + end) / 2;
    if(key < arr[mid]){
        end = mid + 1;
    }else if(key > arr[mid]) {
        start = mid - 1;
    }else {
        return mid;
    }
}
return -1;


正確寫法如下：(迭代過程中，循環不斷減小。)


int start = 0;
int end = arr.length-1;
while(start <= end) {
    int mid = (start + end) / 2;
    if(key < arr[mid]){
        end = mid - 1;
    }else if(key > arr[mid]) {
        start = mid + 1;
    }else {
        return mid;
    }
}
return -1;

感謝各位的閱讀，以上就是“java二分搜索算法常見使用誤區是什么”的內容了，經過本文的學習后，相信大家對java二分搜索算法常見使用誤區是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！