溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Java分治法與二分搜索算法。分享給大家供大家參考，具體如下：
1、分治法
分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題相互獨立且與原問題相同。遞歸的解這些子問題，然后將各子問題的解合并得到原問題的解。
分治法所能解決的問題一般具有以下幾個特征：
1) 該問題的規模縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。
3) 利用該問題分解出的子問題的解可以合并為該問題的解；
4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
分治法的基本步驟：
分治法在每一層遞歸上都有三個步驟：
分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
合并：將各個子問題的解合并為原問題的解。
它的一般的算法設計模式如下：
Divide-and-Conquer(P) if |P|≤n0 then return(ADHOC(P)) //將P分解為較小的子問題 P1 ,P2 ,...,Pk for i←1 to k do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi T ← MERGE(y1,y2,...,yk) △ 合并子問題 return(T)
其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC(P)是該分治法中的基本子算法，用于直接解小規模的問題P。因此，當P的規模不超過n0時直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是該分治法中的合并子算法，用于將P的子問題P1,P2 ,...,Pk的相應的解y1,y2,...,yk合并為P的解。
子問題的劃分：人們從大量實踐中發現，在用分治法設計算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取 k = 2。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
2、二分搜索
大部分程序員應該都知道二分搜索的大致原理，這里不再贅述。需要說明的是二分搜索是所有以比較為基礎的搜索算法時間復雜度最低的算法。用二叉樹描速二分查找算法，最壞情況下與二叉樹的最高階相同。比較二叉樹線性查找也可用二叉樹表示，最壞情況下比較次數為數組元素數量。任何一種以比較為基礎的搜索算法，其最壞情況所用時間不可能低于O(logn)。
二分搜索程序清單如下：
import java.util.Scanner;
public class BinarySearch {
public static int BinarySearch (int[] a,int x,int n) {
int left = 0;
int right = n - 1;
while(left <= right) {
int middle = (left + right) / 2;
if(x == a[middle]) return middle;
if(x >= a[middle]) left = middle + 1;
else right = middle - 1;
}
return -1;
}
public static void main(String args[]) {
System.out.println("億速云測試結果：");
int[] a = new int[10];
for(int i = 0; i < a.length; i++) {
a[i] = i+1;
System.out.print(a[i] + " ");
}
System.out.println();
System.out.println("請輸入你要查詢的數：");
Scanner sc = new Scanner(System.in);
int b = sc.nextInt();
int num = BinarySearch(a, b, a.length) + 1;
System.out.println("要查找的數在第" + num + "個位置");
}
}
運行結果：
更多關于java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
