就个人而言，本身我觉得这个问题都属于人们经过了大量的经验所总结出来的，所以其实我们在分解子问题的时候最好把问题的规模设计为大小都差不多的，通俗的来说：就是把一个问题分解成为大小相同的k个子问题是比较不错的。（事实上这种使子问题大致相同的做法是一种自平衡子问题的思想）。
- 定义：分治法的思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
- 解决方法：我们可以递归的解决这些子问题，然后将这些小的子问题和原问题合并，进而各个击破，达到解决整个原问题的目的！
- 分治算法分解为多少个子问题比较的合适呢？
其实这个问题前人也是经过了很多的经验才发现了在使用分治法设计算法时，最好使子问题的规模大致相同，即讲一个子问题分解为大小相同的k个子问题比较的合适。这种使子问题的 规模大致相同的做法是一种自平衡的思想。并且使用分治法的算法一般是递归的算法。
4.分治法比较常见的一种使用方式（二分搜索算法）
代码段:
//二分搜索算法
public static int binartSearch(int[] arr,int key){
int low = 0;
int high = arr.length-1;
while(low<=high){
int mid = (low+high)/2;
if(key == arr[mid]){
return mid;
}
else if(key < arr[mid]){
high = mid-1;
}else{
low = mid+1;
}
}
return -1;
}
二分搜索思想:就是讲一个长度为n的问题分为大小相同的两个部分，在左右两边进行搜索比较其中的值是否与key相同。如果其中key<arr[mid]那么就在左边这部分进行查找，同理在右边进行查找。
整个算法在最坏的情况下时间复杂度为O(logn)，其实想要写好一个真正的二分算法很不容易，第一个二分算法是在1946年才发现，到了1962年才真正的写出了真正的二分搜索算法！
京公网安备 11010502036488号