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二分查找怎麼實作迭代的詳細內容。更多資訊請關注PHP中文網其他相關文章！