二分查找及改进

在优化程序时偶然看到这篇二分查找常见问题以及《算法珠玑》上的优化算法，但却并不完整.

在自己程序中测试了一下，改为最终的优化版后（也就是《珠玑》上的program4），比program1能提升10%左右，这和具体运算的内容有关～。

如果序列中有多个相同的元素时,查找的时候不见得每次都会返回第一个元素的位置, 比如考虑一种极端情况:序列中都只有一个相同的元素,那么去查找这个元素时,显然返回的是中间元素的位置.

其次, 前面给出的算法中,每次循环体中都有三次情况,两次比较,有没有办法减少比较的数量进一步的优化程序?

<<编程珠玑>>中给出了解决这两个问题的算法,结合前面提到溢出问题对middle的计算也做了修改:

int search(int array[], int n, int v)
{
    int left, right, middle;

    left = -1, right = n;

    while (left + 1 != right)
    {
        middle = left + （right － left) / 2;

        if (array[middle] < v)
        {
            left = middle;
        }
        else
        {
            right = middle;
        }
    }

    if (right >= n || array[right] != v)
    {
        right = -1;
    }

    return right;
}

这个算法是所有这里给出的算法中最完善的一个,正确,精确且效率高.

（转载自www.cppblog.com/converse）

//////////////////////

其实还有更好program4，我改成c++,在array内容为字串情况下，比上面的方法要好10%

如下：

int search(int array[], int n, int v)
{
    int left, middle;
    left = -1;
    middle = 1;
    if(n > 1)
    {
    for(int i=0;;i++)
    {
     if(mid >= n)
     {
       middle = middle>>1;
       break;
     }
     middle = middle<<1;
    }
    }

    if(array[middle-1] < elm)
      left = n - middle;

    while (middle != 1)
    {
        middle = middle>>2;
        if (array[left+middle] < v)
        {
            left = left+middle;
        }
    }

    if (right >= n || array[right] != v)
    {
        right = -1;
    }

    return right;
}

原文链接: https://www.cnblogs.com/BryZ/archive/2011/05/08/2040703.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/25158

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

二分查找及改进

相关推荐