怎么在java中利用二分查找實(shí)現(xiàn)迭代

怎么在java中利用二分查找實(shí)現(xiàn)迭代？相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

Java是什么

Java是一門(mén)面向?qū)ο缶幊陶Z(yǔ)言，可以編寫(xiě)桌面應(yīng)用程序、Web應(yīng)用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應(yīng)用程序。

1.迭代概念

對(duì)一組指令或一定步驟進(jìn)行重復(fù)執(zhí)行稱(chēng)為迭代(iterator)。通俗點(diǎn)說(shuō)，叫一個(gè)個(gè)數(shù)過(guò)去。

實(shí)現(xiàn)這樣一個(gè)個(gè)數(shù)過(guò)去功能的東西，叫迭代器。

2.迭代三要素

1.確定變量

在可以用迭代算法解決的問(wèn)題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。

2.建立關(guān)系式

所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問(wèn)題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來(lái)完成。

3.過(guò)程控制

在什么時(shí)候結(jié)束迭代過(guò)程?這是編寫(xiě)迭代程序必須考慮的問(wèn)題。不能讓迭代過(guò)程無(wú)休止地重復(fù)執(zhí)行下去。迭代過(guò)程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來(lái)；另一種是所需的迭代次數(shù)無(wú)法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來(lái)實(shí)現(xiàn)對(duì)迭代過(guò)程的控制；對(duì)于后一種情況，需要進(jìn)一步分析出用來(lái)結(jié)束迭代過(guò)程的條件。

3.二分查找的迭代實(shí)例

/*非遞歸的折半查找*/
public static int binarySearch(int[] a, int x) {
int left = 0;
int right = a.length - 1;
while(left <= right) {
int mid = (left+ right) / 2;
if(x > a[mid]) {
left = mid+1;
} else if(x < a[mid]) {
right = mid-1;
} else {
return mid;
}
}
return -1;
}

每次迭代在循環(huán)內(nèi)的所有工作話(huà)費(fèi)O(1)，因此分析需要確定循環(huán)的次數(shù)。循環(huán)從right-left=leng-1開(kāi)始并在right-left<= -1結(jié)束。每次循環(huán)后right-left的值至少將該循環(huán)前的值折半；于是，循環(huán)的次數(shù)最多是[log(n-1)]+2。因此：運(yùn)行的時(shí)間是O(log N)，而遞歸的時(shí)間復(fù)雜度則需要O(N)。

看完上述內(nèi)容，你們掌握怎么在java中利用二分查找實(shí)現(xiàn)迭代的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！