数据结构方法之二分查找法

野性酷女 2022-05-22 02:04 240阅读 0赞

一、什么是二分查找法？（略）
    二、二分查找法的性能分析。
    二分查找法的平均查找长度是ASL=log2(n+1)-1 (n>50)
    ★例题：
        对长度为12的有序表（a1,a2,...a12)（其中ai<aj当i<j时），进行折半查找，在假
    定查找不成功时，关键字x<a1,x>a12以及ai<x<aj（i=1,2,..12)等情况发生的概率相等
    ，求查找不成功的平均查找长度是多少？
    解答：一、查找不成功事件的分布律为
    ....──┬──┬────┬────┬──┬──
    .... §.│x<a1│<a1,a2>.│<a2,a3>.│。。│x>a12
    ....──┼──┼────┼────┼──┼──
    .... P..│1/13│1/13....│1/13....│。。│1/13
    ....──┴──┴────┴────┴──┴──
    故查找不成功的数学期望为∑PiCi
    其中断定x<a1需查找3次
    <a1,a2>...4次
    <a2,a3>...4次
    <a5,a6>...4次
    <a4,a5>...4次
    <a3,a4>...3次
    <a6,a7>...3次
    <a7,a8>...4次
    <a8,a9>...4次
    <a10,a11>..4次
    <a9,a10>...4次
    <a11,a12>..4次
    x>a12......4次
    故E=49/13=3.77次
    上面的解法看起来很完备。但是本题很可能以填空题的形式出现，如果按上面的解法，
    则显得太笨拙了。在叙述最佳解法之前，再看一道例题。
    ★假定有序表A[1..20]上进行二分查找，则比较一次查找成功的结点数为__①__,比较三
    次成功的结点数为__②__，比较5次成功的结点数为__③__，平均查找长度为__④__。
    ....解：先给出正确答案：①1,..②4..,③5..④3.7 。其中平均查找长度可由下求得：
    
    ....设折半查找的判定树树深为n，则1→(n-1)都为满二叉树，故有
    ....depth=1→count=1
    ....depth=2→count=2
    ....depth=3→count=4
    ....depth=4→count=8
    ....depth=5→count=20-①-②-③-④=5(此句理解为结点总数减去以上各层结点数）。
    
    ....因此，第一层有一个结点，只需要查找一次即可找到，第二层有两个结点，各需要
    查找二次才能找到；第三层有4个结点，各需要查找3次；....因此总共查找次数为1*1+
    2*2+3*4+4*8+5*5=74,从而平均查找长度为3.7次。
    ◆以上是两个具有一般性的例子，它的一般性在于，我们没有给出具体的序列。仅就有
    序表中元素个数已知这一个条件进行了讨论。这就提示我们，二分查找法进行查找时，
    查找结果与所给序列具体值无关，只与其元素个数有关；具体到查找某个元素的结果，
    则只与该元素在序列中的位置有关。我们拿两个序列为例：
    ★例题：今有有序表A和有序表B，分别是：
    .....A: 1,3,5,20,21,32,57,58,60
    .....B: 1,2,3,4,7,8,18,23,26,30
    .....要查找表A中的关键字32和表B中的关键字18，需要查找几次？
    .....在上面的题中，查找次数只与它们所处的位置有关，所以结果应该是一致的。这里
    我们不给出答案。
    下面我们讨论解二分法查找有关问题的最佳解法——利用二分法查找判定树求解。
    三、二分法查找判定树
    ⒈定义见书。
    ⒉二分查找判定树的画法。
    ....设表A[l,h]是一个有序表。
    ◆一棵二分查找判定树的树形由以下步骤确定：
    ....①取m=(l+h)/2,以m为根，画出该结点；
    ....②取(l,m',m-1)为新有序表，画出m的左子树；取(m+1,m*,h)为新序列，画出右子树
    ；前述m'和m*由下式求得：
    ....m'=(l+m-1)/2；m*=(m+1+h)/2,即公式与最初求m的相同，类似递归定义。
    ....③若l=m，则该结点无左子树；若m=h则该结点无右子树；
    ....④重复上述步骤直到完成。
    ....下面给出一个有11个元素的有序表作二分法查找判树
    的示例：
    ①:m=(1+11)/2=6，画出根结点：.................................⑥
    ............................................................/...\
    ②:取（1,m',5),画出左子树，此时m'=3,即左子树根......(1,3,5)/.....\...L,m*,H
    结点号为3：..............................................③.......⑨(7,9,11)
    ......................................................../..\...../..\
    ③:取（7，m*，11），画出右子树，此时m*=9，即右.(1,1,2)./....\.../....\
    子树根结点号为9.........   ...........................①(445)④.⑦(778)⑩(10,10,11).....
    ........................................................\......\..\......\
    ④：取（1，m',2），画出结点3的左子树，此时m'=1,.........②.....⑤.⑧.....⑾.........
    即左子树根结点号为1（略去对其它结点的讨论）；由于此
    时在(L,m,h）元组中，L=h=1,故此分支作图结束。
    ....在实际作图中，请参考右图中的标记方法，我曾经戏称
    它为关氏标注。它可以使用脱掉上面的步骤。
    ...→(445)属结点④，（778）属结点⑦
    ⒊二分查找判定树的应用
    →求ASL
    →求查找失败时的平均查找长度
    →求查找某结点的查找长度
    ⒋二分查找判定树树形的讨论
    若一棵二分查找判定树树深为H层，则1-（h-1)为满二叉树，第h层上第一个结点为空，
    最后一个结点为满（为什么？请读者思考）。
    ——————————————————————————————————————
    ——————————
    作者注：为帮助读者深入理解二分法查找，我在这里列出了一些基本概念，由于这些基
    本概念书上已讲得很详细，所以从略。列出来是帮读者形成一个完整轮廓，以免断章取
    义。
    视时间和反响而定，这是我数据结构解题方法第一篇，以后可能不定期推出续篇，也可
    能这是最后一篇。这个系列致力于找出一切可能的最简解题方法。
    作者声明保留一切权利。不保证全部观点正确及演算无误。

===============================================================================================

在学习算法的过程中，我们除了要了解某个算法的基本原理、实现方式，更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间，我们又会更注重时间复杂度。 时间复杂度按优劣排差不多集中在： O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n) 到目前位置，似乎我学到的算法中，时间复杂度是O(log n),好像就数二分查找法，其他的诸如排序算法都是 O(n log n)或者O(n2)。但是也正是因为有二分的 O(log n), 才让很多 O(n2)缩减到只要O(n log n)。   关于二分查找法 二分查找法主要是解决在“一堆数中找出指定的数”这类问题。 而想要应用二分查找法，这“一堆数”必须有一下特征：
     
      
       存储在数组中
       有序排列
      所以如果是用链表存储的，就无法在其上应用二分查找法了。（曽在面试被问二分查找法可以什么数据结构上使用：数组？链表？） 至于是顺序递增排列还是递减排列，数组中是否存在相同的元素都不要紧。不过一般情况，我们还是希望并假设数组是递增排列，数组中的元素互不相同。   二分查找法的基本实现 二分查找法在算法家族大类中属于“分治法”，分治法基本都可以用递归来实现的，二分查找法的递归实现如下：
     
      
      
       int bsearch(int array[], int low, int high, int target)
    {
        
        if (low > high) return -1;
        
        int mid = (low + high)/2;
        if (array[mid]> target)
            return    binarysearch(array, low, mid -1, target);
        if (array[mid]< target)
            return    binarysearch(array, mid+1, high, target);
        
        //if (midValue =http://www.cnblogs.com/ider/archive/2012/04/01/= target)
            return mid;
    }
     
        不过所有的递归都可以自行定义stack来解递归，所以二分查找法也可以不用递归实现，而且它的非递归实现甚至可以不用栈，因为二分的递归其实是尾递归，它不关心递归前的所有信息。
     
      
      
       int bsearchWithoutRecursion(int array[], int low, int high, int target)
    {
        
        while(low <= high)
        {
        
            int mid = (low + high)/2;
            if (array[mid] > target)
                high = mid - 1;
            else if (array[mid] < target)
                low = mid + 1;
            else //find the target
                return mid;
        }
        //the array does not contain the target
        return -1;
    }
     
        只用小于比较（<）实现二分查找法 在前面的二分查找实现中，我们既用到了小于比较（<）也用到了大于比较（>），也可能还需要相等比较（==）。 而实际上我们只需要一个小于比较（<）就可以。因为错逻辑上讲a>b和b<a应该是有相当的逻辑值；而a==b则是等价于 !((a<b)||(b<a))，也就是说a既不小于b，也不大于b。 当然在程序的世界里， 这种关系逻辑其实并不是完全正确。另外，C++还允许对对象进行运算符的重载，因此开发人员完全可以随意设计和实现这些关系运算符的逻辑值。 不过在整型数据面前，这些关系运算符之间的逻辑关系还是成立的，而且在开发过程中，我们还是会遵循这些逻辑等价关系来重载关系运算符。 干嘛要搞得那么羞涩，只用一个关系运算符呢？因为这样可以为二分查找法写一个template，又能减少对目标对象的要求。模板会是这样的：  
     
      
      
       template <typename T, typename V>
    inline int BSearch(T& array, int low, int high, V& target)
    {
        
        while(!(high < low))
        {
        
            int mid = (low + high)/2;
            if (target < array[mid])
                high = mid - 1;
            else if (array[mid] < target)
                low = mid + 1;
            else //find the target
                return mid;
        }
        //the array does not contain the target
        return -1; 
    }
     
      我们只需要求target的类型V有重载小于运算符就可以。而对于V的集合类型T，则需要有[]运算符的重载。当然其内部实现必须是O(1)的复杂度，否则也就失去了二分查找的效率。   用二分查找法找寻边界值 之前的都是在数组中找到一个数要与目标相等，如果不存在则返回-1。我们也可以用二分查找法找寻边界值，也就是说在有序数组中找到“正好大于（小于）目标数”的那个数。 用数学的表述方式就是：      在集合中找到一个大于（小于）目标数t的数x，使得集合中的任意数要么大于（小于）等于x，要么小于（大于）等于t。   举例来说： 给予数组和目标数
     
      
      
       int array = {
        2, 3, 5, 7, 11, 13, 17};
    int target = 7;
     
      那么上界值应该是11，因为它“刚刚好”大于7；下届值则是5，因为它“刚刚好”小于7。 用二分查找法找寻上届
     
      
      
       //Find the fisrt element, whose value is larger than target, in a sorted array 
    int BSearchUpperBound(int array[], int low, int high, int target)
    {
        
        //Array is empty or target is larger than any every element in array 
        if(low > high || target >= array[high]) return -1;
        
        int mid = (low + high) / 2;
        while (high > low)
        {
        
            if (array[mid] > target)
                high = mid;
            else
                low = mid + 1;
            
            mid = (low + high) / 2;
        }
    
        return mid;
    }
     
      与精确查找不同之处在于，精确查找分成三类：大于，小于，等于（目标数）。而界限查找则分成了两类：大于和不大于。 如果当前找到的数大于目标数时，它可能就是我们要找的数，所以需要保留这个索引，也因此if (array[mid] > target)时 high=mid; 而没有减1。 用二分查找法找寻下届
     
      
      
       //Find the last element, whose value is less than target, in a sorted array 
    int BSearchLowerBound(int array[], int low, int high, int target)
    {
        
        //Array is empty or target is less than any every element in array
        if(high < low  || target <= array[low]) return -1;
        
        int mid = (low + high + 1) / 2; //make mid lean to large side
        while (low < high)
        {
        
            if (array[mid] < target)
                low = mid;
            else
                high = mid - 1;
            
            mid = (low + high + 1) / 2;
        }
    
        return mid;
    }
     
      下届寻找基本与上届相同，需要注意的是在取中间索引时，使用了向上取整。若同之前一样使用向下取整，那么当low == high-1，而array[low] 又小于 target时就会形成死循环。因为low无法往上爬超过high。   这两个实现都是找严格界限，也就是要大于或者小于。如果要找松散界限，也就是找到大于等于或者小于等于的值（即包含自身），只要对代码稍作修改就好了： 去掉判断数组边界的等号：
     
      
      
       target >= array[high]改为 target > array[high]
     
      在与中间值的比较中加上等号：
     
      
      
       array[mid] > target改为array[mid] >= target
     
        用二分查找法找寻区域 之前我们使用二分查找法时，都是基于数组中的元素各不相同。假如存在重复数据，而数组依然有序，那么我们还是可以用二分查找法判别目标数是否存在。不过，返回的index就只能是随机的重复数据中的某一个。 此时，我们会希望知道有多少个目标数存在。或者说我们希望数组的区域。 结合前面的界限查找，我们只要找到目标数的严格上届和严格下届，那么界限之间（不包括界限）的数据就是目标数的区域了。  
     
      
      
       //return type: pair<int, int>
    //the fisrt value indicate the begining of range,
    //the second value indicate the end of range.
    //If target is not find, (-1,-1) will be returned
    pair<int, int> SearchRange(int A[], int n, int target) 
    {
        
        pair<int, int> r(-1, -1);
        if (n <= 0) return r;
        
        int lower = BSearchLowerBound(A, 0, n-1, target);
        lower = lower + 1; //move to next element
        
        if(A[lower] == target)
            r.first = lower;
        else //target is not in the array
            return r;
        
        int upper = BSearchUpperBound(A, 0, n-1, target);
        upper = upper < 0? (n-1):(upper - 1); //move to previous element
        
        //since in previous search we had check whether the target is
        //in the array or not, we do not need to check it here again
        r.second = upper;
        
        return r;
    }
     
      它的时间复杂度是两次二分查找所用时间的和，也就是O(log n) + O(log n)，最后还是O(log n)。   在轮转后的有序数组上应用二分查找法 之前我们说过二分法是要应用在有序的数组上，如果是无序的，那么比较和二分就没有意义了。 不过还有一种特殊的数组上也同样可以应用，那就是“轮转后的有序数组（Rotated Sorted Array）”。它是有序数组，取期中某一个数为轴，将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲，有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。 下边就是二分查找法在轮转后的有序数组上的实现（假设数组中不存在相同的元素）  
     
      
      
       int SearchInRotatedSortedArray(int array[], int low, int high, int target) 
    {
        
        while(low <= high)
        {
        
            int mid = (low + high) / 2;
            if (target < array[mid])
                if (array[mid] < array[high])//the higher part is sorted
                    high = mid - 1; //the target would only be in lower part
                else //the lower part is sorted
                    if(target < array[low])//the target is less than all elements in low part
                        low = mid + 1;
                    else
                        high = mid - 1;
    
            else if(array[mid] < target)
                if (array[low] < array[mid])// the lower part is sorted
                    low = mid + 1; //the target would only be in higher part
                else //the higher part is sorted
                   if (array[high] < target)//the target is larger than all elements in higher part
                        high = mid - 1;
                    else
                        low = mid + 1;
            else //if(array[mid] == target)
                return mid;
        }
    
        return -1;
    }
     
      对比普通的二分查找法，为了确定目标数会落在二分后的那个部分，我们需要更多的判定条件。但是我们还是实现了O(log n)的目标。   二分查找法的缺陷 二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上： 必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。 数组读取效率是O(1)，可是它的插入和删除效率却是O(n2)。因而导致构建有序数组变成低效的事情。   解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是自平衡二叉查找树了，自能高效的（O(log n)）构建有序元素集合，又能如同二分查找法一样快速的搜寻目标数。