# 12.分治：利用分治法完成数据查找

分治法的核心思想就是‘分而治之’。利用分而治之的思想，可以把一个大规模、高难度问题，分解为若干小规模、低难度小问题。再将若干小问题各个击破；再将这些简单小问题的答案合并，就是原问题的答案。

分治法应用很广泛，很多高效率算法都是以分治法做为其基础思想，例如：排序算法中的快速排序和归并排序

# 12-1 分治法是什么？

问题说涉及的数据规模越小，所需时间也越少，反之亦然

例子：在一个包含n个元素的无序数组中，要求按照从小到大的顺序打印其n个元素

当n=1时，不需要任何计算
当n=2时，需要做一个比较
当n=3时，需要做3次比较
当n=10时，需要做45次比较((n(n-1))/2)

所以，分治法的核心思想就是分而治之；具体就是：将一个难解决的大问题，分割为一些可以直接解决的小问题。分割后如果无法解决，就继续递归分割，直到每个小问题都可以解决
这些子问题具备互相独立、形式相同的特点。这样，我们就可以采用同一种解法，递归地去解决这些子问题，最后再将每个子问题的解合并，就得到原问题的解。

# 12-2 分治法的价值

例子:在1000个有序数字构成的数组a中，判断某个数字c是否出现过

第一种方法：全局遍历，复杂度O(n)
第二种方法：采用二分查找法，复杂度为O(logn)

小数据规模上，两种方法对时间的消耗几乎一样，分治法也没有体现出特殊价值，无非就是代码更牛一点

再看一个例子：假如有一张厚度为1毫米且足够柔软的纸，问将它对折多少次后，厚度能达到地球到月球的距离
根据计算，如果使用二分查找法，仅仅只需要39次判断，就能达到这个结果，复杂度为O(logn)相比复杂度为O(n)的算法，在大数据集合中性能有着爆发式的提高

# 12-3 分治法的使用方法

当你使用分治法时，一般原问题都需要具备以下几个特征：

1.难度在降低：原问题的解决难度，随着数据的规模的缩小而降低
2.问题可分：原问题可以分解为若干规模较小的同类型问题
3.解可合并：利用所有子问题的解，可合并出原问题的解(重要)
4.互相独立：各个子问题之间相互独立，某个子问题的求解不会影响到另一个子问题

分治法在每轮递归上，都包含了分解问题、解决问题和合并结果这3个步骤注意：二分查找是利用分治法去查找解决，通常二分查找需要一个前提，那就是输入的数列是有序的

二分查找的思路比较简单，步骤如下：

1.选择一个标致i将集合L分为二个子集合，一般可以使用中位数
2.判断标致L(i)是否能与要查找的值des相等，相等则直接返回结果
3.如果不相等，需要判断L(i)和des的大小
4.基于判断的结果决定下步是向左还是向右查找，如果某个方向查找的空间为0，这返回结果未查到
5.回到步骤1

# 12-4 分治法的案例

例子：在数组[1,2,3,4,5,6,7,8,9,10]中查找8是否出现过
下面用代码解决

 function main(){
    //需要查找的数字
    let targetNumber = 8;
    //数组
    let arr = [1,2,3,4,5,6,7,8,9,10];
    //中位数
    let middle = 0;
    // 最初值
    let low = 0;
    //数组长度-1
    let high = arr.length - 1;
    //查询结果
    let isfind = 0;
    //循环结束条件
    while(low < high){
      //取中位数
      middle = Math.ceil((low+high)/2);//会有商不为整数的情况
      //如果中位数等于目标值
      if(arr[middle] == targetNumber){
        document.write(`${targetNumber}在数组中，下标为${middle}`);
        isfind = 1;
        break;
      }else if(arr[middle] > targetNumber){
        //如果中位值大于目标值
        high = middle - 1;//取左侧数组
      }else{
        //如果中位数小于目标值，则取右边值
        low = middle + 1;
      }

    };
    //循环结束，判断isfind的值
    if(isfind == 0){
      document.write(`${targetNumber}不在数组中`);
    }

 }

基于这个例子，可以进行一些规律的总结：

1.二分查找法的时间复杂度为O(logn),这也是分治法普遍具备的特性。当面对某个代码题，而且约束了时间复杂度为O(logn)或者O(nlogn)时，可以想一想分治法是否可行
2.二分查找的循环次数并不确定，一般是达到某个条件就跳出循环。因此，编码时，多数会采用while循环加break跳出代码结构
3.二分查找处理的原问题必须是有序的，因此，当你在一个有序数据环境中处理问题时，可以考虑分治法。相反，如果原问题中数据并不是有序的，则使用分治法的可能性就会很低了

# 12-5 练习题

例子：在一个有序数组中，查找出第一个大于9的数字，假设一定存在，例如：arr = [-1,3,3,7,10,14,14],则返回10

 function main(){
   //目标值
   let targetNumber = 9;
   // 需要查询的数组
   let arr = [-1,3,3,7,10,14,14];
   //定义中位值
   let middle = 0;
   // 定义起始位置
   let low = 0;
   //定义长度-1的值
   let high = arr.length - 1;
   //while循环可行的条件
   while(low <= high){
     middle = Math.ceil((n(n-1))/2);
     //中位数就是目标值,中位数大于目标值 && (没有中值 || 前一个值小于目标值)
     if(arr[middle] > targetNumber && (middle == 0 || arr[middle-1] < targetNumber)){
       document.write(`第一个比${targetNumber}大的数字是${arr[middle]},下标是middle`);
       break;
     }else if(arr[middle] > targetNumber){
       //如果中位值比目标值大，但是前一个值也大
        high = middle - 1;//取前半段
     }else{
       //如果比中位数小，取后半段
       low = middle + 1;
     }
   }
 }

# 12-6 总结

在面对陌生问题时，需要判断问题的数据是否有序
预期的时间复杂度是否带有logn项
是否可以通过小问题的答案合并出原问题的答案
如果以上条件都符合，第一时间使用分治法

← 11.递归：求解汉诺塔问题 13.排序：经典排序算法原理解析与对比 →