二分探索

大量のデータがあった場合。

そっからある特定のIDと合致するデータを探したい…

もし、そのIDの小さい順にならんでいるなら二分法がありますね。

二分法そのものに関してはアルゴリズムの本に載ってます。

さてさて、その二分法をstlで使うならこんなプログラムになりますかね。

下のコードは、Dataというクラスのtrueidをキーにして、探すプログラムです。

ポイントは stlのlower_boundの最後の引数ですね。

自分で定義したDataというクラスの<演算子が定義されていないなら、代替用の関数として別途代入できるわけです。

（定義されていても、用途がちがうってときもあるし）

/**
 * @file main.cpp
 * @author r-suzuki
 * @date 2008-04-01
 */
#include 
#include 
#include 
#include 
using namespace std;

class Data
{
public:
  int	  m_true_id;
  int	 m_inner_id;

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

  void output(void);
};


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;
}

bool compare(const Data& arg1, const Data& arg2)
{
  if( arg1.m_true_id < arg2.m_true_id ) return true;
  return false;
}

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

  for( size_t i = 0; i < nodes.size(); i++){
	nodes[i].output();
  }

  // 讀懃ｴ｢
  vector test;
  test.push_back(1);
  test.push_back(2);
  test.push_back(3);
  binary_search(test.begin(), test.end(), 2);

  
  Data a(4);
  vector::iterator target = lower_bound(nodes.begin(), nodes.end(), a, compare);

  target->output();
  
  return 0;
}