Java分治法與二分搜索算法實例分析

本文實例講述了Java分治法與二分搜索算法。分享給大家供大家參考，具體如下：

1、分治法

分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題相互獨立且與原問題相同。遞歸的解這些子問題，然后將各子問題的解合并得到原問題的解。

分治法所能解決的問題一般具有以下幾個特征：

　 1) 該問題的規(guī)?？s小到一定的程度就可以容易地解決
　 2) 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
　 3) 利用該問題分解出的子問題的解可以合并為該問題的解；
　 4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

分治法的基本步驟：

分治法在每一層遞歸上都有三個步驟：

　　分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；
　　解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題；
　　合并：將各個子問題的解合并為原問題的解。

它的一般的算法設(shè)計模式如下：

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的規(guī)模；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時，問題已容易直接解出，不必再繼續(xù)分解。ADHOC(P)是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。因此，當(dāng)P的規(guī)模不超過n0時直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是該分治法中的合并子算法，用于將P的子問題P1,P2 ,...,Pk的相應(yīng)的解y1,y2,...,yk合并為P的解。

子問題的劃分：人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取 k = 2。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。

2、二分搜索

大部分程序員應(yīng)該都知道二分搜索的大致原理，這里不再贅述。需要說明的是二分搜索是所有以比較為基礎(chǔ)的搜索算法時間復(fù)雜度最低的算法。用二叉樹描速二分查找算法，最壞情況下與二叉樹的最高階相同。比較二叉樹線性查找也可用二叉樹表示，最壞情況下比較次數(shù)為數(shù)組元素數(shù)量。任何一種以比較為基礎(chǔ)的搜索算法，其最壞情況所用時間不可能低于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("億速云測試結(jié)果：");
    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("請輸入你要查詢的數(shù)：");
    Scanner sc = new Scanner(System.in);
    int b = sc.nextInt();
    int num = BinarySearch(a, b, a.length) + 1;
    System.out.println("要查找的數(shù)在第" + num + "個位置");
  }
}

運行結(jié)果：

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設(shè)計有所幫助。