学步园

/*算法总结
  二分查找法:
  二分查找法的前提是数据已经排序,时间平均复杂度为 O(lgn)
  欢迎转载,转载请注明作者 openxmpp@163.com
*/


#include <iostream>
#include <stdio.h>
using namespace std;
#include <vector>
using std::vector;
#include <algorithm>


/**
 * @brief binarySearch 二分查找
 * @param array 排序后的数组
 * @param value 待查找的参数
 * @return true on success ,false on failure
 */
template<typename T>
bool binarySearch(vector<T> &array,T value)
{
    int low = 0;
    int high = array.size () -1;
    while ( low <= high )
    {
        int middle = ( low + high ) /2;
        if ( array[middle] == value )
        {
            return true;
        }
        else if ( array[middle] > value )
        {
            high = middle - 1;
        }
        else if ( array[middle] < value )
        {
            low = middle + 1;
        }
    }
    return false;
}


void unitTest()
{
    vector<int> vec;
    for ( int i = 0 ; i < 100 ; i += 2 )
    {
        vec.push_back (i);
    }
    bool result = binarySearch<int>(vec,29);
    cout << "search result for [29]  " << result<<endl;
    result = binarySearch<int>(vec,16);
    cout << "search result for [16]  " << result<<endl;


    vector<string> strVect;
    strVect.push_back ("world");
    strVect.push_back ("hello");
    strVect.push_back ("b");
    strVect.push_back ("a");
    strVect.push_back ("i love cpp");
    sort(strVect.begin (),strVect.end ());


    result = binarySearch<string>(strVect,"notfind");
    cout << "search result for [notfind]  " << result<<endl;


    result = binarySearch<string>(strVect,"world");
    cout << "search result for [world]  " << result<<endl;
}


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





下面是递归的实现
#include <iostream>
using namespace std;

template<typename T>
int
bSearch( T array[], T value,int start,int end )
{
    if ( start > end )
    {
        return -1;
    }
    int middle = (start + end)/2;
    if ( array[middle] == value )
    {
        return middle;
    }
    else if ( array[middle] > value )
    {
        return bSearch(array,value,start,middle-1);
    }
    else if ( array[middle] < value )
    {
        return bSearch(array,value,middle+1,end);
    }
}

int main(int argc, char *argv[])
{
    int array[] = {1,2,3,4,5,6,7,8,10,12,32,45};
    int index = bSearch(array,7,0,sizeof(array)/sizeof(array[0])-1);
    cout << index << " " << array[index]<<endl;
    index = bSearch(array,12,0,sizeof(array)/sizeof(array[0])-1);
    cout << index << " " << array[index]<<endl;
    return 0;
}