分治法（算法）

分���法是算法常用的解题方法之一，是将一个大的问题拆分为若干小的问题。二分法就是常用的分治法。

可以采用分治法解决的一些问题：

1.二分查找

2.合并排序（归并排序）

3.快速排序

4.快速幂

5.汉诺塔

一、二分查找

二分查找对要查找的序列有两个要求：

​ 一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以）

​ 二是该序列必须是顺序存储的。

例题：二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

思路：

1、先确定中间位置：

　　　　middle = (left+right)/2;

2、将待查找得值与nums[middle]的值相比较。若相等，则查找成功并返回该位置，否则须确定新确定查找区间，继续查找。

3、如果nums[middle] 的值大于待查找的值，则证明在nums[middle]~nums[right]中所有的值都大于待查找的值，令right=middle，在nums[left]到nums[middle]中查找。

4、当left>right时，证明nums中没有要查找的值，跳出循环，返回-1。

代码实现：

class Solution {  public int search(int[] nums, int target) {​    int left=0;​    int right=nums.length-1;​    int middle;​    while(lefttarget)​        right=middle-1;​      else​        left=middle+1;​    }​    return -1;  }}

java

二、合并排序（归并排序）

归并排序是基于递归实现的，归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将数据分为a，b两组，再将a，b各自再分成两组，以此类推，当每一组都只有一个数据时，认为这个小小组已经达到了有序，再将相邻两个小小组依次合并。

例题：排序数组

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]

输出：[1,2,3,5]

思路：

1、将数组进行拆分，利用递归的方法，将数组拆分成一个个单独的元素。

2、依次对数组进行合并，依次比较数组内的元素，将较小的元素先加入新的数组，依次往下比较，如果一个数组内的值已经全都加入新数组，将另一个数组的剩下的值依次加入新数组。

3、将额外的空间覆盖掉原来的空间。

代码实现：

class Solution {    int[] tmp; //定义临时数组    public int[] sortArray(int[] nums) {        tmp = new int[nums.length];        mergeSort(nums, 0, nums.length - 1); //进入递归        return nums;    }    public void mergeSort(int[] nums, int l, int r) {        if (l >= r) {            return;        //当l>=r时，每个区间里面只有一个数值        }        int mid = (l + r) /2;    //均分区间        mergeSort(nums, l, mid);    //对左侧区间进行划分        mergeSort(nums, mid + 1, r); //对右侧区间进行划分        int i = l, j = mid + 1;            int cnt = 0;        while (i