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

這篇文章主要介紹“java二分查找怎么實(shí)現(xiàn)迭代”的相關(guān)知識，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“java二分查找怎么實(shí)現(xiàn)迭代”文章能幫助大家解決問題。

1.迭代概念

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

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

2.迭代三要素

1.確定變量

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

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

所謂迭代關(guān)系式，指如何從變量的前一個值推出其下一個值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通常可以使用遞推或倒推的方法來完成。

3.過程控制

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

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

關(guān)于“java二分查找怎么實(shí)現(xiàn)迭代”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。