Algorithm問題を解く 7 - Hashキーで検索

問題

Let A be a sorted array of integers and S a target integer.

Design an efficient algorithm for determining if there exist
a pair of indices i,j (not ncessarily distinct) such that A[i] + A[j] = S.
( Algorithms for interview より引用 )

ヒント

sorted array .. ２分探索？２分探索でも勿論解ける．しかしバイナリサーチより効率の良いアルゴリズムは？

解答1

適当にループで回してもO(N^2)で解を出すことはできるが，もう一工夫．
バイナリサーチで検索の範囲を狭めれば良くてO((N/2)^2)，悪くてO(N^2)となる．

#include <iostream>
#include <vector>
#include <map>
using namespace std;

void init_vector(vector<int>& v) {
 v.push_back( 5 );
 v.push_back( 8 );
 v.push_back( 12 );
 v.push_back( 20 );
 v.push_back( 33 );
 v.push_back( 45 );
 v.push_back( 53 );
 v.push_back( 64 );
 v.push_back( 80 );

}

int search_max(const vector<int>& v, int s) {

 int min = 0;
 int max = v.size() - 1;
 int mid;
 int midval;
 bool found = false;
 
 // pre .. if s is less than v[0], no way to find pair.
 if( s <= *(v.begin()) )
  throw "not qualify pre-requisite";
  

 while( min <= max ) {
  mid = (min + max) / 2;
  midval = v.at(mid);
  if( s == midval ) {
   found = true;
   break;
  }
  else if( s > midval) {
   min = mid + 1;
  }
  else {
   max = mid - 1;
  }
 }

 return found ? mid : max;
}

bool search(const vector<int>& v, int s) {
 
 int max;
 try {
  max = search_max(v,s);
  cout << "max for search:" << max << endl;
 }catch(const char* msg) {
  cerr << "errmsg:" << msg << endl;
  return false;
 }

 for( int i = 0;i < max;i++ ) {
  for( int j = i;j < max;j++ ) {
   if( v[i] + v[j] == s ) 
    return true;
  }
 }

 return false;

}

void dump(const vector<int>& v) {
 
 for( vector<int>::const_iterator iter = v.begin();iter != v.end();iter++ ) {
  cout << *iter << endl;
 }

}


int main()
{
 vector<int> v;
 init_vector(v);
 dump(v);
 try {
  cout << search(v,3) << endl;
 } catch( const char* err) {
  cerr << err << endl;
 }

 cout << search(v,55) << endl;
 cout << search(v,53) << endl;

 return 0;
}

解答2

プログラムは長くなった割に得たものは少ない．ならばアプローチを変えよう． 目的の数Sからループ中の要素v[i]を引いてcを得る．そのcがハッシュテーブルにあれば(O(1)オーダで検索可)，v[i]+v[j]=Sを満たすのである． プログラムは非常にすっきりするし，オーダもO(N)である．

bool search2(const vector<int>& v, int s ) {
 map<int,int> m;
 vector<int>::const_iterator iter;
 int c;
 int i;
 for(i = 0,iter = v.begin();iter != v.end();iter++,i++) {
  c = s - v[i];
  m[v[i]] = i;
  if( m.find( c ) != m.end() )
   return true;
 }
 return false;

}