C++11写算法之二分查找

浏览数：36 / 时间：2015年06月08日

同样的，二分查找很好理解，不多做解释，要注意二分查找的list必须是排好序的。

这里实现了两种二分查找的算法，一种递归一种非递归，看看代码应该差不多是秒懂。想试验两种算法，改变一下findFunc函数指针（auto findFunc = RecursionBinaryFind; //BinaryFind ）即可。

时间复杂度：O(lgn)

空间复杂度：O(1)

除了顺序查找和二分查找，还有一些需要借助某些数据结构才能进行查找的算法，例如：分块查找，二叉排序树查找，哈希查找，B树/B+树/B*树查找等，这些算法的重点更偏向于数据结构本身，因而将放在数据结构部分进行示例。

show me the code ！

// #if __cplusplus < 201103L 
// #error "must be compiled under c++11 support platform!!!"
// #endif
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cassert>
using namespace std;

//WARNING : input varList of function RecursionBinaryFind must be sorted!!!
int RecursionBinaryFindImp(const int varList[], const int begin,const int end, const int target)
{
    if (!varList || begin > end)
    {
        return -1;
    }
    int index = -1;
    int mid = (begin + end) >> 1;

    if (target == varList[mid])
    {
        index = mid;
    }
    else if (target < varList[mid])
    {
        index = RecursionBinaryFindImp(varList,begin,mid - 1,target);
    }
    else if (target > varList[mid])
    {
        index = RecursionBinaryFindImp(varList, mid + 1, end, target);
    }

    return index;
}
int RecursionBinaryFind(const int varList[], const int size, const int target)
{
    if (!varList || size < 0)
    {
        return -1;
    }
    return RecursionBinaryFindImp(varList,0,size-1,target);
}

//WARNING : input varList of function SequentialFind must be sorted!!!
int BinaryFind(const int varList[], const int size, const int target)
{
    if (!varList || size < 0)
    {
        return -1;
    }
    int index = -1;
    int begin = 0;
    int end = size - 1;
    int mid = (begin + end) >> 1;
    while (begin<end)
    {
        if (target == varList[mid])
        {
            break;
        }else if (target < varList[mid])
        {
            end = mid - 1;
        }else if (target > varList[mid])
        {
            begin = mid + 1;
        }
        mid = (begin + end) >> 1;
    }
    index = mid;
    return index;
}

void test()
{
    //case counter
    int testCase = 0;
    //find function object
    auto findFunc = RecursionBinaryFind; //BinaryFind
    //show case result lambda function
    auto showFunc = [&testCase](){cout << "case[" << testCase++ << "] ok... "<<endl; };

    cout << "test begin : " << endl << endl;

    //case empty list
    {
        assert(-1 == findFunc(nullptr, 0, 0));
        showFunc();
    }
    //case wrong list size
    {
        const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 };
        assert(-1 == findFunc(testList, 0, 0));
        showFunc();
    }
    //case not found
    {
        const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 };
        const int size = sizeof(testList) / sizeof(int);
        const int target = -33;
        assert(-1 == findFunc(testList, 0, 0));
        showFunc();
    }
    //case found at begin position
    {
        const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 };
        const int size = sizeof(testList) / sizeof(int);
        const int target = -12;
        assert(0 == findFunc(testList, size, target));
        showFunc();
    }
    //case found at random position
    {
        const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 };
        const int size = sizeof(testList) / sizeof(int);
        const int target = 1;
        assert(3 == findFunc(testList, size, target));
        showFunc();
    }
    //case found at end position
    {
        const int testList[] = { -12, -3, 0, 1, 2, 3, 12, 34, 56 };
        const int size = sizeof(testList) / sizeof(int);
        const int target = 56;
        assert(size - 1 == findFunc(testList, size, target));
        showFunc();
    }

    cout <<endl<< "test done ! " << endl << endl;
}

int main(int argc, char* argv[])
{
    test();
    return 0;
}