二分搜索算法

古城微笑少年丶 2022-06-17 22:48 163阅读 0赞

二分搜索算法是计算机程序设计中的基础算法，1946年第一篇二分搜索算法的论文发表，第一个正确的算法实现是在1962年，中间相隔16年，这一事实令人深思。据了解训练有素的程序员仅有10%的人能够在数小时内写出完全正确的代码实现。因此，我也进行了尝试。现将实现如下贴出，不能保证完全正确，欢迎批评指正。

BinarySearch.h

#ifndef BinarySearch_H
    #define BinarySearch_H
    #include <assert.h>
    template<class T>
    T *binarySearch(T value,T a[],int left,int right,int *index)
    {
        assert(a);
        if (left > right)
        {
            *index = -1;
            return NULL;
        }
        int mid = (right + left)/2;
        if (value == a[mid])
        {
            *index = mid;
            return &a[mid];
        }
        else if (value < a[mid])
        {
            return binarySearch(value,a,left,mid-1,index);
        }
        else if (value > a[mid])
        {
            return binarySearch(value,a,mid+1,right,index);
        }
    }
    
    template<class T>
    T *binSearch(T value,T a[],int n,int *index)
    {
        assert(a);
        int left = 0;
        int right = n-1;
        int mid;
        while (left <= right)
        {
            mid = (left+right)/2;
            if (a[mid] == value)
            {
                *index = mid;
                return &a[mid];
            }
            else if (a[mid] > value)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        *index = -1;
        return NULL;
    }
    #endif

main.cc

using namespace std;
    template <class T>
    void output(T a[],int n);
    int main()
    {
        int a[] = {-5,-3,0,0,2,2,2,2,6,8};
        int n = sizeof(a)/sizeof(a[0]);
        cout << "The a[] ";
        output(a,n);
        int index;
    
        int test[] = {-6,-5,-3,0,0,1,2,2,2,2,6,8,9};
        int len = sizeof(test)/sizeof(test[0]);
        int i;
        cout << "The test[] ";
        output(test,len);
        cout << "递归二分搜索算法" <<endl;
        for (i = 0;i < len;i++)
        {
            if (binarySearch(test[i],a,0,n-1,&index)==NULL)
            {
                cout << test[i] << " The index is null" << endl;
                continue;
            }
            cout << *binarySearch(test[i],a,0,len-1,&index) << " ";
            cout <<"The index is:"<< index << endl;
        }
        cout << "循环二分搜索算法" <<endl;
        for (i = 0;i < len;i++)
        {
            if (binSearch(test[i],a,n,&index)==NULL)
            {
                cout << test[i] << " The index is null" << endl;
                continue;
            }
            cout << *binSearch(test[i],a,len,&index) << " ";
            cout <<"The index is:"<< index << endl;
        }
        return 0;
    }
    
    template <class T>
    void output(T a[],int n)
    {
        assert(a);
        int i = 0;
        for (; i < n; i++)
            cout << a[i] <<" ";
        cout << endl;
    }

makefile

main:main.o
            g++ -o main main.o
    main.o:main.cc BinarySearch.h
            g++ -c main.cc
    clean:
            rm -f main *.o *.s *.i *.gch

执行 make命令，./main结果

root@duyuqi-OptiPlex-380:~/DataStruct/Algorithms/search# make
    g++ -c main.cc
    g++ -o main main.o
    root@duyuqi-OptiPlex-380:~/DataStruct/Algorithms/search# ./main
    The a[] -5 -3 0 0 2 2 2 2 6 8 
    The test[] -6 -5 -3 0 0 1 2 2 2 2 6 8 9 
    递归二分搜索算法
    -6 The index is null
    -5 The index is:0
    -3 The index is:1
    0 The index is:2
    0 The index is:2
    1 The index is null
    2 The index is:6
    2 The index is:6
    2 The index is:6
    2 The index is:6
    6 The index is:8
    8 The index is:9
    9 The index is null
    循环二分搜索算法
    -6 The index is null
    -5 The index is:0
    -3 The index is:1
    0 The index is:2
    0 The index is:2
    1 The index is null
    2 The index is:6
    2 The index is:6
    2 The index is:6
    2 The index is:6
    6 The index is:8
    8 The index is:9
    9 The index is null