算法练习：分治法_分治法进阶练习

分治法

• 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
• 精髓：
  分–将问题分解为规模更小的子问题；
  治–将这些规模更小的子问题逐个击破；
  合–将已解决的子问题合并，最终得出“母”问题的解；
• 可解决问题的特征

1. 该问题的规模缩小到一定的程度就可以容易地解决
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3. 利用该问题分解出的子问题的解可以合并为该问题的解；
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

• 生活实例
  在一堆硬币中有一个是假币，重量较真币轻，若两两相比费时费力。采用分治法，将硬币分成两堆相比，将轻的那一堆再分成两堆相比……
• 经典应用
  1. 折半搜索
  折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。

public static int binarysearch(int[] num,int x){
   
		int L=0;
		int R=num.length-1;
		while(L<=R) {
   
			int mid=L+(R-L)/2;//不要用（L+R）/2，有可能溢出int
			if(x==num[mid]) return mid;	
			else if(x>num[mid]) L=mid+1;
			else R=mid-1;
		}
		return -1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。步骤如下：
1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2）设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3）比较两个指针所指向的元素，选择较小的元素放入到合并空间，并移动指针到下一位置；
4） 重复步骤 3 直到某一指针达到序列尾；
5）将另一序列剩下的所有元素直接复制到合并序列尾。

public static void GB(int[] arr,int start,int end,int[] help) {
   
		if(start<end) {
   
			int mid=start+(end-start)/2;
			GB(arr,start,mid,help);
			GB(arr,mid+1,end,help);
			HB(arr,start,mid,end,help);
		}
		
	}
	public static void HB(int[] arr, int start
1
2
3
4
5
6
7
8
9
10
11