简单_分治算法

分治算法，多么简单的思想！可是它无处不在。btree,b+树中都有它的身影！

1、分治算法：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

2、二分法：利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一种有效的方法，例如二分法检索。

3、解题步骤：分治法解题的一般步骤：
　　（1）分解，将要解决的问题划分成若干规模较小的同类问题；
　　（2）求解，当子问题划分得足够小时，用较简单的方法解决；
　　（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

4、实例说明：
a)、利用分治算法求最大最小数：

package sunfa.idea;

import java.util.Arrays;

/**
 * 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，
 * 我们往往先把它分解成几个子问题
 * ，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题
 * ，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。
 * 
 */
public class BranchDemo1 {

	public static void main(String[] args) {
		BranchDemo1 demo1 = new BranchDemo1();
		int[] a = { 1, 3, 2, 4, 5, 6, 3, 2, 10, 12, 9 };
		Arrays.sort(a);
		System.out.println(Arrays.toString(a));
		demo1.simpleMinMax(a);
		System.out.println("branchMinMax:");
		MinMaxBean bean = branchMinMax(a, 0, a.length-1);
		System.out.println("max:" + bean.max + ",min:" + bean.min);
	}

	// 普通算法
	public static void simpleMinMax(int[] a) {
		MinMaxBean bean = new MinMaxBean();
		bean.max = a[0];
		bean.min = a[0];
		for (int i = 1; i < a.length; i++) {
			if (bean.max < a[i])
				bean.max = a[i];
			if (bean.max < a[i])
				bean.min = a[i];
		}
		System.out.println("max:" + bean.max + ",min:" + bean.min);
	}

	//分治算法求最大最小数
	public static MinMaxBean branchMinMax(int[] a, int low, int hihg) {
		MinMaxBean bean = new MinMaxBean();
		//2 求解
		if (low > hihg - 2) {//如果问题规模较小，此处小于等于2个则直接求解
			if (a[low] < a[hihg]) {
				bean.max = a[hihg];
				bean.min = a[low];
			} else {
				bean.max = a[low];
				bean.min = a[hihg];
			}
			System.out.println("区间["+low+","+hihg+"] [max:"+bean.max+",min:"+bean.min+"]");
		} else {//否则对问题进行分解
			int mid = (low + hihg) >>> 1;  //1 分解
			//3  合并
			MinMaxBean b1 = branchMinMax(a, low, mid);
			MinMaxBean b2 = branchMinMax(a, mid + 1, hihg);
			bean.max = b1.max > b2.max ? b1.max : b2.max;
			bean.min = b1.min < b2.min ? b1.min : b2.min;
		}
		return bean;
	}
}

class MinMaxBean {
	int max;
	int min;
}

b)利用二分法查找数组中某个数或对象的索引
java.util.Arrays源码：

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
				     int key) {
	int low = fromIndex;
	int high = toIndex - 1;

	while (low <= high) {
	    int mid = (low + high) >>> 1;
	    int midVal = a[mid];

	    if (midVal < key)
		low = mid + 1;
	    else if (midVal > key)
		high = mid - 1;
	    else
		return mid; // key found
	}
	return -(low + 1);  // key not found.
    }

在对象数组中的二分法查找：

private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
				     Object key) {
	int low = fromIndex;
	int high = toIndex - 1;

	while (low <= high) {
	    int mid = (low + high) >>> 1;
	    Comparable midVal = (Comparable)a[mid];
	    int cmp = midVal.compareTo(key);

	    if (cmp < 0)
		low = mid + 1;
	    else if (cmp > 0)
		high = mid - 1;
	    else
		return mid; // key found
	}
	return -(low + 1);  // key not found.
    }

评论

2 楼 hardPass 2012-01-10  

貌似二分法，没有一个合并的过程

1 楼 zhufeng1981 2011-10-29  

讲解的不错，支持一下。