四、二分检索和分治算法

二分检索是针对有序表的检索。所谓有序表，是指线性表中的所有数据元素按关键码值的某种次序进行递增或递降的排列。二分检索法的基本思想是：每次将待查区间中间位置上的数据元素的关键码值与给定值K比较，若不等则缩小检索区间并在新的区间内重复上述过程，直到检索成功或检索区间长度为0（检索不成功）为止。
    二分检索法的效率可以通过二分检索的决策树进行衡量。其平均检索长度与最大检索长度相近，效率较高。但它要求被检索序列事先按关键码的次序（递增或递减）排列，而排序本身是一种很费时的运算；另外，二分检索只适用于顺序存储结构，而在顺序结构中插入和删除都比较困难。因此，二分检索特别适用于那种一经建立就很少改动、而又需要经常检索的线性表。
    现以有序表（15，17，18，22，35，51，60，88，93）为例说明用二分检索算法查找K=18的过程（这里假定表中各元素只含关键码）。首先，取整个有序表为检索区间，这通过分别置low、high为1、9来完成。
    因区间长度大于0，取区间中间位置mid = (1+9)/2 = 5，将mid位置上元素的关键码值35与K=18比较。因18<35，将区间缩小为[1，4]。注意此新区间与原区间[1，9]的差别仅在于上界不同，修改区间的工作可通过修改上界high = mid－1=5－1完成。
    由于循环终止条件未满足，重复上述过程。这时区间中点为mid=(1+4)/2=2，比较结果18>17表明区间应改为[3，4]，这一修改由下界的修改low = mid+1=2+1完成。
    再次进行比较时，区间中点为mid=(3+4)/2=3，比较结果表明dataList[mid]正是待查元素，检索成功，返回结果为mid=3。(如下图所示）

分治法思想：
    一般而言，计算机求解问题的规模越小，所需的计算时间也越少。对于规模为N的问题，分治策略将其分解为k（k = 2, 3, 4, …，一般取k=2）个相同类型的子问题，每个子问题的规模相对较小且相互独立；递归地求解这些子问题，并将所得结果合并而求出原来问题的解。这就是分治策略的基本思想。
    分治策略算法通常分为三个部分:分割、求解、合并。