コード#コード#

#include 
#include "std_lib_facilities.h" 

using namespace std;

/* my binary search function */
template
bool my_binary_search(ForwardIterator first, ForwardIterator last, const T& value)
{
    
    int size = distance(first, last);
    int lo = 0;
    int hi = size - 1;
    int mid;
        
    while(lo <= hi) {
        mid = lo + (hi-lo)/2;   
        if(*(first+mid) < value) lo = mid + 1;
        else if(*(first+mid) > value) hi = mid - 1;
        else {  return true; }
    }
    return false;
}


struct Test {
    string label;
    int val;
    vector seq;
    bool res;
};


void print_Test(Test& t){
    cout << endl <<  "Read: ";
    cout << "{ " << t.label << " " << t.val
        << " " << " { ";
    for(auto& p : t.seq)
        cout << p << " " ;
    cout << " } " << t.res << " } " << endl;
}

istream& operator>>(istream& is, Test& t) // use the described format
{
    // Example input: { 27 7 { 1 2 3 5 8 13 21} 0 }
    string a, b;

    if (is >> a >> t.label >> t.val >> b && (a != "{" || b != "{"))
    {
        std::cerr << "ERROR: Invalid test file format" << std::endl;
        return is;
    }

    //cout << a << '|' << t.label << '|'  << b << '|'  << t.val << '|' ;

    t.seq.clear();
    std::copy(
        std::istream_iterator(is),
        std::istream_iterator(),
        std::back_inserter(t.seq)
    );

    is.clear();

    //std::copy(t.seq.begin(), t.seq.end(), std::ostream_iterator(cout," "));
    string c, d;
    int res = 0;

    if (is >> c >> res >> d && (c != "}" || d != "}"))
    {
        std::cerr << "ERROR: Invalid test file format" << std::endl;
        return is;
    }

    t.res = res;
    //cout << c << '|' << t.res << '|' << d << '|' ;

    return is;
}


int test_all(istream& is)
{
    int error_count = 0;
    Test t;
    while(is >> t) {
    
        bool r = my_binary_search(t.seq.begin(), t.seq.end(), t.val);
    
        if (r !=t.res) {
            cout << "failure: test " << t.label
            << " binary_search: "
            << t.seq.size() << " elements, val==" << t.val
            << " -> " << t.res << '
';
            ++error_count;
            }
    }

    return error_count;
}


int main()
{
    ifstream ist {"my_tests.txt"};
    Test t;
    ist >> t;
    int errors = test_all(ist);
    cout << "number of errors: " << errors << "
";
}

入力

// my_tests.txt
{ 1.1 1 { 1 2 3 5 8 13 21 } 1 }
{ 1.2 5 { 1 2 3 5 8 13 21 } 1 }
{ 1.3 8 { 1 2 3 5 8 13 21 } 1 }
{ 1.4 21 { 1 2 3 5 8 13 21 } 1 }
{ 1.5 -7 { 1 2 3 5 8 13 21 } 0 }
{ 1.6 4 { 1 2 3 5 8 13 21 } 0 }
{ 1.7 22 { 1 2 3 5 8 13 21 } 0 }
{ 2.1 1 { } 0 }
{ 3.1 1 { 1 } 1 }
{ 3.2 0 { 1 } 0 }
{ 3.3 2 { 1 } 0 }

しゅつりょく

number of errors: 0

説明

wikibook[3]を参照して、自分で書いた二分検索関数を試します.

[1]この本のテストコードを使用しました.

は[2]このヘッダファイルstd_lib_facilities.hをインポートする必要がある.

template
bool my_binary_search(ForwardIterator first, ForwardIterator last, const T& value)
{
    
    int size = distance(first, last); //[4] std::distance
    int lo = 0;
    int hi = size - 1;
    int mid;
        
    while(lo <= hi) {
        mid = lo + (hi-lo)/2;   
        if(*(first+mid) < value) lo = mid + 1;
        else if(*(first+mid) > value) hi = mid - 1;
        else {  return true; }
    }
    return false;
}

疑問???

なぜか分からない.1行目の入力データを飲み込んだ???

リファレンス

[1] Programming -- Principles and Practice Using C++ (Second Edition) http://www.stroustrup.com/Programming/[2] std_lib_facilities.h http://www.stroustrup.com/Programming/PPP2code/std_lib_facilities.h [3] Binary Search Algorithm https://en.wikibooks.org/wiki/Algorithm_Implementation/Search/Binary_search [4] std::distance http://en.cppreference.com/w/cpp/iterator/distance [5] binary search in STL http://en.cppreference.com/w/cpp/algorithm/binary_search