Algorithm 問題を解く5 - インターセクション

問題

Given sorted arrays A and B of lengths n and m respectively, return an array C containing elements common to A and B. The array C should be free of duplicates. How would you perform this intersection if - (1.) n = m and (2.) n < m?
( 出典: Algorithms for interviews )

ヒント

これは典型的なインターセクションの問題である．ソート済みとくれば勿論あのアルゴリズムが頭をよぎるのではないだろうか．

解

逐次ループを回して配列nとmの共通要素を括りだしていけば簡単に解を得ることができるが，当然効率の面からみてよくない．O(n*m)である．ならば両配列がソート済みというヒントに注目したい．このヒントは明らかに２分探索して要素を探りなさい，といっているではないか．

コードは以下の通り．注意すべきは短い配列を最初のループにすること．O(N*log2M)とO(M*log2N)では大きな差となってしまう．

#include <iostream>
#include <cstdlib>
using namespace std;

static char arrA[] = { 'A','B','B','E','G', 'K', 'U' };
static char arrB[] = { 'C','D','E','F','G', 'K', 'V','Z' };


void dump(char* arr, int size){

 for(int i = 0;i < size;i++){
  cout << arr[i] << ' ';
 }
 cout << endl;
}

void my_bsearch(char arr[], char target, int* idx){

 cout << "bsearching.." << endl;
 int min = 0;
 int max = sizeof(arrB)/sizeof(char) - 1;
 char midVal;

 while(min <= max){
  midVal = arrB[(min + max) / 2];
  cout << target << ',' << min << ',' << max << ',' << midVal << ',' << (min + max)/2 << endl;
  if(midVal == target) {
   arr[*idx] = midVal;
   *idx += 1;
   return;
  }
  else if(midVal < target)
   min = (min + max)/2 + 1;
  else
   max = (min + max)/2 - 1;

 }

}

int main() {

 char ansArr[100];
 int delta = 0;
 int idx = 0;
 
 for(int i = 0;i < sizeof(arrA)/sizeof(char);i++){
  my_bsearch(ansArr, arrA[i], &idx);
 }

 cout << "idx.." << idx << endl;
 dump(ansArr, idx);


 return EXIT_SUCCESS;
}