4/10/2008

Binary Search with STL

I have used large data with c++.
Something to do while I use large data is to find target data.

Large data is arranged with order of rise.

Therefore I appropriated Binary Search to algorithm finding target data.

This way is efficient, Processing time became small.

Next codes are Binary Search with stl in c++.

#include < algorithm >
#include < iostream >
#include < list >
using namespace std;

class Data
{
public:
  int m_true_id;
  int m_inner_id;

  Data(int ti = -1, int ii = -1);

  void output(void);
  bool operator < (const Data& arg){
    if( this->m_true_id > arg.m_true_id ) return true;
    return false;
  }
};


Data::Data(int ti, int ii) :
m_true_id(ti),
m_inner_id(ii)
{
}

void Data::output(void)
{
  cout << "Data[" << m_true_id << "]" << endl;
  cout << endl;
}


int main(void)
{
  list< Data > nodes;
  for(int i =0; i < 10; i++){
   nodes.push_back(Data(i));
  }

  for( list< Data >::iterator ite = nodes.begin(); ite != nodes.end(); ite++){
    (*ite).output();
  }


  list< Data >::iterator target
= lower_bound(nodes.begin(), nodes.end(), a);

  target->output();


  return 0;
}


Keypoint is define operator < in class Data.

No comments: