算法实践：https://github.com/JackieLong/algorithms

常见查找算法：https://github.com/JackieLong/interview#%E6%9F%A5%E6%89%BE

二分查找

SearchAlgorithm.h

  2. namespace SearchAlgorithm
  3. {
  4.     enum Algorithm
  5.     {
  6.         Binary,
  7.         Binary_Recur,
  8.     };
  10.     // 拆半查找算法（循环版）
  11.     template<class T, class Comp>
  12.     int binarySearch( T t[], const int &data_size, const T &value, Comp comp )
  13.     {
  14.         int start = 0, end = data_size - 1, mid = -1;
  16.         while( start <= end )
  17.         {
  18.             mid = ( start + end ) >> 1;
  19.             if( t[mid] == value ) { return mid; }
  20.             else if( comp( t[mid], value ) ) {  start = mid + 1; }
  21.             else { end = mid - 1; }
  22.         }
  23.         return -1;
  24.     }
  26.     // 拆半查找算法（递归版）
  27.     template<class T, class Comp>
  28.     int binarySearch_recur( T t[], const int &data_size, const T &value, Comp comp )
  29.     {
  30.         if( data_size <= 0 ) { return -1; }
  31.         int mid = ( 0 + data_size - 1 ) >> 1;
  32.         if( t[mid] == value ) { return mid; }
  33.         else if( comp( t[mid], value ) ) { return _binarySearch_recur( t, data_size, value, mid + 1, data_size - 1, comp ); }
  34.         else { return _binarySearch_recur( t, data_size, value, 0, mid - 1, comp ); }
  35.     }
  37.     template<class T, class Comp>
  38.     int _binarySearch_recur( T t[], const int &data_size, const T &value, const int &start, const int &end, Comp comp )
  39.     {
  40.         if( start > end ) { return -1; }
  41.         int mid = ( start + end ) >> 1;
  42.         if( t[mid] == value ) { return mid; }
  43.         else if( comp( t[mid], value ) ) { return _binarySearch_recur( t, data_size, value, mid + 1, end, comp ); }
  44.         else { return _binarySearch_recur( t, data_size, value, start, mid - 1, comp ); }
  45.     }
  46. }

测试用例

  1. #include "TestSearchAlgorithm.h"
  3. void main()
  4. {
  5.     // ***************************************************************
  6.     //
  7.     // 测试查找算法
  8.     //
  9.     // ***************************************************************
  10.     TestSearchAlgorithm testSearch;
  11.     testSearch.test( SearchAlgorithm::Algorithm::Binary );
  12.     testSearch.test( SearchAlgorithm::Algorithm::Binary_Recur );
  13. }

TestSearchAlgorithm.h

  2. #include "SearchAlgorithm.h"
  4. class TestSearchAlgorithm
  5. {
  6.     using Algorithm = SearchAlgorithm::Algorithm;
  7. public:
  8.     void test( const Algorithm algorithm );
  9. };

TestSearchAlgorithm.cpp

  2. #include "TestSearchAlgorithm.h"
  3. #include <functional>
  4. #include <algorithm>
  5. #include <map>
  6. #include <random>
  7. #include <iostream>
  9. void TestSearchAlgorithm::test( const Algorithm algorithm )
  10. {
  11.     using T        = int;
  12.     using Comp     = std::function<bool( const int &, const int & )>;
  13.     using SearchFunc = std::function<int( T t[], const int &len, const T &value, Comp comp )>;
  14.     using std::placeholders::_1;
  15.     using std::placeholders::_2;
  16.     using std::placeholders::_3;
  17.     using std::placeholders::_4;
  19.     std::map<Algorithm, SearchFunc> algorithmMap;
  20.     algorithmMap[Algorithm::Binary]       = std::bind( &SearchAlgorithm::binarySearch<T, Comp>, _1, _2, _3, _4 );
  21.     algorithmMap[Algorithm::Binary_Recur] = std::bind( &SearchAlgorithm::binarySearch_recur<T, Comp>, _1, _2, _3, _4 );
  23.     // *****************************************************
  24.     // 随机生成一个升序的int数组，size=100。
  25.     // *****************************************************
  26.     static std::default_random_engine e;
  27.     static std::uniform_int_distribution<int> u( 1, 100 );
  29.     const int data_size = 100;
  30.     T a[data_size];
  31.     int last = 0;
  32.     int tmpRandomInt = 0;
  33.     for( int i = 0; i < data_size; i++ )
  34.     {
  35.         while( !tmpRandomInt ) { tmpRandomInt = u( e ); }
  36.         a[i] = last + tmpRandomInt;
  37.         last = a[i];
  38.         tmpRandomInt = 0;
  39.     }
  41.     // *****************************************************
  42.     // 输出随机数组
  43.     // *****************************************************
  44.     for( int i = 0; i < data_size; i++ ) printf( "[%d]%d ", i, a[i] );
  45.     std::cout << std::endl << std::endl;
  47.     // *****************************************************
  48.     // 多次查找数组中随机的目标数，输出查找结果
  49.     // *****************************************************
  50.     static std::uniform_int_distribution<int> randomIndex( 0, data_size );
  52.     int tmpTargetIdx;
  53.     int tmpTarget = 0;
  54.     for( int i = 0; i < data_size; i++ )
  55.     {
  56.         tmpTarget    = a[randomIndex( e )];
  57.         tmpTargetIdx = algorithmMap[algorithm]( a, data_size, tmpTarget, []( const int &a, const int &b ) {return a < b; } );
  58.         printf( "result of searching target(%d) is a[%d] = %d\n", tmpTarget, tmpTargetIdx, a[tmpTargetIdx] );
  59.     }
  60. }