溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“java二分查找怎么實現迭代”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“java二分查找怎么實現迭代”文章能幫助大家解決問題。
1.迭代概念
對一組指令或一定步驟進行重復執行稱為迭代(iterator)。通俗點說，叫一個個數過去。
實現這樣一個個數過去功能的東西，叫迭代器。
2.迭代三要素
1.確定變量
在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。
2.建立關系式
所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。
3.過程控制
在什么時候結束迭代過程?這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對于前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對于后一種情況，需要進一步分析出用來結束迭代過程的條件。
3.二分查找的迭代實例
/*非遞歸的折半查找*/
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;
}每次迭代在循環內的所有工作話費O(1)，因此分析需要確定循環的次數。循環從right-left=leng-1開始并在right-left<= -1結束。每次循環后right-left的值至少將該循環前的值折半；于是，循環的次數最多是[log(n-1)]+2。因此：運行的時間是O(log N)，而遞歸的時間復雜度則需要O(N)。
關于“java二分查找怎么實現迭代”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
