溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
怎么在java中利用二分查找實現迭代？相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
Java是一門面向對象編程語言，可以編寫桌面應用程序、Web應用程序、分布式系統和嵌入式系統應用程序。
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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
