java二分搜索算法常見(jiàn)使用誤區(qū)是什么

這篇文章主要講解了“java二分搜索算法常見(jiàn)使用誤區(qū)是什么”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“java二分搜索算法常見(jiàn)使用誤區(qū)是什么”吧！

直接使用二分搜索法，搜索一個(gè)無(wú)序的數(shù)組或集合。
 
如果你運(yùn)氣好的話，可能會(huì)搜索到你想要的數(shù)據(jù)，但是大部分情況下你不能得到你想要的結(jié)果。因?yàn)槎炙阉魇前凑罩虚g值來(lái)計(jì)算你要搜索數(shù)據(jù)的范圍，每次逐漸縮小范圍。如果你的結(jié)果不在一個(gè)按照升序排列的數(shù)組中，你要搜索的數(shù)據(jù)很可能被遺棄，然后返回負(fù)值。我們可以通過(guò)如下所示一段程序來(lái)斷言，數(shù)組是否是有序的。
 
for(int i=0; i< arr.length; i++) {
    if(arr[i]>arr[i+1]) {
        return 0
    }
    return 1;
}
 

自己寫(xiě)了一個(gè)二分搜索算法，陷入了一個(gè)死循環(huán)，不知道為什么？


 因?yàn)槟愕倪吔鐩](méi)有完全控制好，所以造成了這種情況。如下:


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

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;

如上這種寫(xiě)法看起貌似是正確的，如果仔細(xì)分析的話，會(huì)發(fā)現(xiàn)數(shù)組的長(zhǎng)度為7

* 第一次循環(huán)中間量mid=3

* 第二次循環(huán)中間量mid=4

* 第三次循環(huán)中間量mid=5

* 第四次循環(huán)中間量mid=6

* 第五次循環(huán)中間量mid=6

* 第六次循環(huán)中間量mid=6

* 第七次循環(huán)中間量mid=6
* .....
* 由此陷入死循環(huán)

反面教材 2：
如果我們通過(guò)調(diào)試之后，把程序調(diào)整成如下，循環(huán)搜索結(jié)果，發(fā)現(xiàn)依然是個(gè)死循環(huán)。最終卡在了中間值5上，究其原因是因?yàn)?，我們的中間值不能一直縮小，所以最終導(dǎo)致這個(gè)問(wèn)題。

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;


正確寫(xiě)法如下：(迭代過(guò)程中，循環(huán)不斷減小。)


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二分搜索算法常見(jiàn)使用誤區(qū)是什么”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)java二分搜索算法常見(jiàn)使用誤區(qū)是什么這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！