关键词：
前言： 分治法 ：divide and conquer 又称分而治之，是一种非常有用的算法设计策略，它是将一个难以解决的大问题规模划分为一些规模较小的子问题，分别求解每个子问题的解，然后合并子问题的解。理所当然，设计分治法需要分三个步骤：
（1）divide 划分，把问题规模划分为k个规模较小的子问题，（一般k=2）
（2）conquer 治，即递归（recursive）地解决子问题
（3）combine 合并子问题的解
关于步骤（1）划分问题规模一般k=2是基于平衡子问题的启发式思想，它几乎总是比子问题规模不等的做法好。
在第二步解决子问题我们谈到递归，这也是一个依据，一个问题规模划分到什么程度才能非常方便的求解？这就是递归设计思想中的平凡问题和子问题。当一个问题规模不断划分直到成为一个平凡问题时（也就是递归基），我们可以在O(1)时间内完成该问题的求解。举个例子
1 int sum(int a[],int n) 2 3 return (n<1)?0:sum(a,n-1)+a[n-1]; 4
没错就是一个简单的数组求和，却蕴含着递归思想，以及分治算法思想
从上面的代码分析和案例分析中，我们看到了分治法的魅力所在，其实在数据结构中，关于内部排序最常用的两个算法 归并排序和快速排序，都是采用了分治法思想设计的，下一篇博文我来讲解一下对此两种算法的认识，在结束之前，我们先热身一下，分析二分查找算法
binary search 二分查找，是在已递增排序好的数组中找给定的x元素是否存在，它也用到了分治思想，我按照分治法设计三步骤给大家剖析一下
（1）divide 分，就是把给定的x和数组中间那个元素比较
（2）conquer 如果x<middle，则只在左子数组中递归查找；否则，只在右子数组中递归查找即recursivly only in one subarray
（3） combine 可是说是没有合并子问题解这一步骤，因为只需要比较找到即可返回布尔值就行
首先我们都知道递归是需要设计平凡问题的，否则无法确定如何停止递归，就本问题而言，每次都是在subarray中查找，如果subarray长度<=0，即不存在子数组时，表示递归基
具体算法实现如下：
1 bool binarySearch(int a[],int x,int low,int high)
2
3 if(low>high)
4 return false;
5 int mid=(low+high)>>1;
6 if( a[mid]==x)
7 return true;
8 else if(a[mid]<x)
9 binarySearch(a,x,mid+1,high);
10 else
11 binarySearch(a,x,low,mid-1);
12
分析该算法时间复杂度
T(n)=1 * O(n/2)+O(1);
这是因为每次递归解决子问题比较之后都只会在一个子区间进行查找，且每次比较都是常数性的。
下一篇会分析二分查找与一般分治算法时间复杂度的不同。
二分算法思想在实际生活中也有应用，比如求解一些只在一个子区间递归解决问题的复杂问题。
算法复习_分治算法之二分搜索棋盘覆盖快速排序(代码片段)
... 一、基本概念 分治法，顾名思义，即分而治之的算法，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…… 二、基本思想及策略 设计思想：将一个难以... 查看详情
六中常用算法设计：穷举法分治法动态规划贪心法回溯法和分支限界法(代码片段)
算法设计之六种常用算法设计方法1.直接遍历态（穷举法） 程序运行状态是可以遍历的，遍历算法执行每一个状态，最终会找到一个最优的可行解；适用于解决极小规模或者复杂度线性增长，而线... 查看详情
排序算法之归并排序(代码片段)
排序算法之归并排序算法思维归并排序（Mergesort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解... 查看详情
重温基础算法内部排序之快速排序法(代码片段)
...章目录内部排序之快速排序法主要思想过程演示JAVA代码算法分析时间复杂度分析最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度对冒泡排序的一种优化主要思想快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。... 查看详情
重温基础算法内部排序之快速排序法(代码片段)
...章目录内部排序之快速排序法主要思想过程演示JAVA代码算法分析时间复杂度分析最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度对冒泡排序的一种优化主要思想快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。... 查看详情
递归与分治策略(代码片段)
递归算法精讲🥇前言：🥈递归的概念🥉基本概念：🥉算法实例：🥈分治法的基本思想🥇前言：对于计算机科学来说，算法的概念至关重要。例如，在一个大型软件系统的开发中&#x... 查看详情
计算机算法设计与分析之递归与分治策略——二分搜索技术(代码片段)
递归与分治策略二分搜索技术 我们所熟知的二分搜索算法是运用分治策略的典型例子，针对这个算法，先给出一个简单的案例。 目的：给定已排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定的元素x。 我们首... 查看详情
分治策略(代码片段)
递归与分治策略递归的概念一个直接或间接地调用自身的算法成为递归算法。在计算机算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。有些数据如二叉树等，由于本身固有的递归特性，特别适... 查看详情
经典算法之棋盘覆盖问题--分治法(代码片段)
一：算法分析棋盘覆盖问题要求在2^k*2^k个方格组成的棋盘中，你给定任意一个特殊点，用一种方案实现对除该特殊点的棋盘实现全覆盖。建立模型如图：解决方案就是利用分治法，将方形棋盘分成4部分，... 查看详情
1-5算法设计常用思想之穷举法(代码片段)
穷举法又称穷举搜索法，是一种在问题域的解空间中对所有可能的解穷举搜索，并根据条件选择最优解的方法的总称。数学上也把穷举法称为枚举法，就是在一个由有限个元素构成的集合中，把所有元素一一枚举研究的方法。使... 查看详情
六中常用算法设计：穷举法分治法动态规划贪心法回溯法和分支限界法(代码片段)
算法设计之六种常用算法设计方法1.直接遍历态（穷举法） 程序运行状态是可以遍历的，遍历算法执行每一个状态，最终会找到一个最优的可行解；适用于解决极小规模或者复杂度线性增长，而线... 查看详情
chatgpt教你算法——分治法(代码片段)
...题和循环赛日程安排问题。1.什么是分治法分治法是一种算法设计技巧 查看详情
图解排序算法之归并排序(代码片段)
...;MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补... 查看详情
图解排序算法之归并排序(代码片段)
...排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)... 查看详情
基础算法分治法之合并排序
思想：合并排序算法的分治策略是将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。 1#include<stdio.h>23voidmerge(inta[],intp,intq,intr)4{5intn1=q-p+1,n2... 查看详情
算法：用分治法设计gray码
...的串，相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。算法设计：n=1时，Gray码：0，1n=2时，Gray码：00，10，11，01 n=3时，Gray码：000，010，011，001，101，111，110，100 n=4,时，Gray码：0 查看详情
数据结构与算法之深入解析常用的七大算法设计策略
...①基本思想在计算机科学中，分治法是一种很重要的算法，字面上的解释是“分而治之”，就是将一个难以直接解决的大问题，分割成n个规模较小的子问题，这些子问题相互独立，且与原问题相同，然... 查看详情
算法设计《分治法》归并排序实例分析之逆序对数
问题定义： 假设A[1...n]是一个有n个不同数的数组。若i<j且A[i]>A[j]则称(A[i],A[j])为数组A的一个逆序对。例如数组<2,3,8,6,1>有(2,1)，(3,1)，(8,6)，(8,1)和(6,1)5个逆序对。对于这个问题，直观上进行求解的话，使用暴力求解... 查看详情