# Algorithm Problem:Intersection of Sorted Array

By | 2012 年 12 月 16 日

Binary search every element of arr1 in arr0, if find, append it to the output. And at each step, shrink the search range.

Intersection of Sorted Array
Find out the intersection of two sorted array

Code

<

pre>

//
// main.cpp
// Intersection of two Sorted Array
//
// Created by Qiu Xiangyu on 12-12-16.
//
// Find out the intersection of two sorted array.

# include

using namespace std;

vector getIntersection(vector &arr0, vector &arr1) {
vector ret;
if (arr0.size() == 0 || arr1.size() == 0) {
return ret;
}

```size_t low = 0;
for (size_t i1 = 0; i1 < arr1.size(); ++i1) {
int v1 = arr1[i1];
//1.find the arr1[0] in arr0 using binary search
{
size_t l = low,h = arr0.size() - 1;
while (l <= h) {
size_t m = (l + h) /2;
if (arr0[m] < v1) {
l = m + 1;
} else if (arr0[m] > v1) {
h = m - 1;
} else {
i0 = m;
break;
}
}
}
if (i0 == -1) {
continue;
} else {
//2.in case there is repeat values in arr0, move i0 towards 0 while arr0[i0] == arr1[0]
while (i0 > low && arr0[i0-1] == arr1[0]) {
--i0;
}
low = i0 + 1;
ret.push_back(v1);
}
}

return ret;```

}

int main(int argc, const char * argv[])
{

```vector<int> arr0 = {0,1,2,3,4,5,5,6,7,8,9,10};
vector<int> arr1 = {5,5,7,9};
vector<int> inte = getIntersection(arr0, arr1);
for (int i = 0; i < inte.size(); ++i) {
cout<<inte[i]<<",";
}
cout<<endl;
return 0;```

}