No. 24 - Intersection of Sorted Arrays

findIntersectionFromSortedArray.cpp

//http://codercareer.blogspot.kr/2011/11/no-24-intersection-of-sorted-arrays.html
//timecomplexity : O(nlogm)
//spacecompexity : O(n)?
#include <vector>
#include <iostream>
#include <algorithm>

int arr1[7] = {1, 3, 5, 7, 9, 10, 15};
int arr2[5] = {3, 5, 7, 11, 16};

using namespace std;

void getIntersectionFromSortedArray(const vector<int> &array1,
                                    const vector<int> &array2,
                                    vector<int> &intersection) {
  intersection.clear();
 
  vector<int>::const_iterator iter1 = array1.begin();
  while(iter1 != array1.end())
  {
      if(binary_search(array2.begin(), array2.end(), *iter1))
        intersection.push_back(*iter1);
      iter1++;
  }

}

int main(void) {
  vector<int> inter;
  vector<int> a(arr1, arr1 + sizeof(arr1)/sizeof(int));
  vector<int> b(arr2, arr2 + sizeof(arr2)/sizeof(int));

  getIntersectionFromSortedArray(a, b, inter);

  //result should be 3, 5, 7
  for(vector<int>::iterator it = inter.begin(); it != inter.end(); it++) {
    cout << *it << " ";
  }
  cout << endl;

  return 0;
}