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

更新時間：2017年11月21日 10:24:35 作者：萌神哆啦A夢

這篇文章主要介紹了Java分治法與二分搜索算法,簡單講述了分治法與二分搜索算法的原理并結(jié)合java實例分析了二分搜索算法的實現(xiàn)與使用技巧,需要的朋友可以參考下

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

1、分治法

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

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

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

分治法的基本步驟：

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

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

它的一般的算法設計模式如下：

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

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

2、二分搜索

大部分程序員應該都知道二分搜索的大致原理，這里不再贅述。需要說明的是二分搜索是所有以比較為基礎的搜索算法時間復雜度最低的算法。用二叉樹描速二分查找算法，最壞情況下與二叉樹的最高階相同。比較二叉樹線性查找也可用二叉樹表示，最壞情況下比較次數(shù)為數(shù)組元素數(shù)量。任何一種以比較為基礎的搜索算法，其最壞情況所用時間不可能低于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é)果：