vector의 이분 검색 알고리즘

#include <iostream>

#include <vector>

#include <string>

#include "base/tools.hpp"



using namespace std;



class Test

{

    public:

        int id;

        string name;

    public:

    Test(int _id,string _name)

    {

        id = _id;

        name = _name;

    }

};



int get(int key,vector<Test>::iterator begin_it,vector<Test>::iterator end_it,vector<Test>::iterator & it)

{

    end_it -= 1;

    vector<Test>::iterator mid_it = begin_it + (end_it-begin_it)/2;

    int count = 0;

    while(begin_it <= end_it)

    {

        count++;

        if(mid_it->id == key)

        {

            it=mid_it;

            cout<<"total search count:"<<count<<endl;

            return true;

        }

        else

        {

            if(mid_it->id < key)

            {

                begin_it = mid_it + 1;

            }

            else

            {

                end_it = mid_it - 1;

            }

        }

        mid_it = begin_it + (end_it - begin_it)/2;

    }

    it = end_it;

    return false;

}



template<typename T> bool get2(int key,T begin_it,T end_it,T & it)

{

    end_it -= 1;

    //typename vector<T>::iterator mid_it = begin_it + (end_it-begin_it)/2;

    T mid_it = begin_it + (end_it-begin_it)/2;

    int count = 0;

    while(begin_it <= end_it)

    {

        count++;

        if(mid_it->id == key)

        {

            it=mid_it;

            cout<<"total search count:"<<count<<endl;

            return true;

        }

        else

        {

            if(mid_it->id < key)

            {

                begin_it = mid_it + 1;

            }

            else

            {

                end_it = mid_it - 1;

            }

        }

        mid_it = begin_it + (end_it - begin_it)/2;

    }

    it = end_it;

    return false;

}



int main()

{

    vector<Test> vect;

    for(int i = 0;i<10000000;i++)

    {

        Test test(i,int_to_str(i));

        vect.push_back(test);

    }

    //sort(vect.begin(),vect.end());

    cout<<"vector has builded!"<<endl;

    clock_t start,finish;

    start = clock();

    /*

    vector<Test>::iterator it = vect.begin();

    while(it!=vect.end())

    {

        if(it->id == 9999999)

        {

            cout<<"id:"<<it->id<<"\tname:"<<it->name<<endl;

            break;

        }

        it++;

    }

    */

    vector<Test>::iterator it;

    if(get(99999,vect.begin(),vect.end(),it))

    {

        cout<<"id:"<<it->id<<"\tit->name:"<<it->name<<endl;

    }

    else

    {

        cout<<"not found!"<<endl;

    }



    finish = clock();

    cout<<"       (s):"<<(double)(finish-start)/CLOCKS_PER_SEC<<"
";



}