首頁 > Java > java教程 > 主體

java二分查找怎麼實作迭代

WBOY
發布: 2023-05-29 20:33:01
轉載
1045 人瀏覽過

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中文網其他相關文章!

相關標籤:
來源:yisu.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板