计算机二分法的算法步骤-五大常用算法之一：分治算法，算法数据结构 五大常用算法

计算机二分法的算法步骤-五大常用算法之一：分治算法，算法数据结构 五大常用算法 分治算法是一种常用的算法设计方法，它将一个规模为n的问题P分解成k个规模较小的子问题，这些子问题相互独立，并且与原来的问题结构相同。在解决这些子问题时，再用相同的方式对每个子问题进行一步的分解，直到某个阈值n0为止。递归地解这些子问题，再把各个子问题的解合并起来，就得到原来问题的解。 分治算法的基本思想是将问题分解成较小的子问题，然后递归地解这些子问题，最后把各个子问题的解合并起来。其中，Adhoc(p(n))是该分治法中的基本子算法，用于直接解小规模的问题P。Merge(y1, y2, ...,yk)是该分治法中的合并子算法，用于将P的子问题P1、P2、…、Pk的相应的解y1、y2、…、yk合并为P的解。 在设计分治算法时，需要注意的问题是如何将问题分解成适合的子问题。一般来说，将问题分解成规模相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。 经典例子1：最大最小问题。假设有一个袋子中有n个金块，共n块。将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一个比较重量的仪器，我们希望用最少的比较次数找到最重和最轻的金块。 算法分析：这个问题可以转化为一个具有n个元素的数组中，寻找最大和最小元素的问题。一般算法是遍历数组，依次将每个元素和当前最大、最小值判断，直到遍历数组结束，返回最大、最小值。但是，这个算法的比较次数是2n-2。用分治法可以较少比较次数地解决这个问题。 例2：二分法求方程近似解。求方程f(x) = x^3 + x^2 - 1 = 0在[0,1]上的近似解，精确度为0.01。算法分析：二分法求方程近似解的基本思想：将方程的有解区间平分为两个小区间，然后判断解在哪个小区间；继续把有解的区间一分为二进行判断，如此周而复始，直到求出满足精确要求的近似解。 二分法求方程近似解的算法步骤是：（1）确定区间[a,b]，验证f(a).f(b) < 0，给定精确度e；（2）求区间(a, b)的中点mid；（3）计算f(mid)；（4）判断是否达到精确度e：即若|a-b| < e，则得到零点近似值a(或b)；否则重复（2）-（4）。