# 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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//
// 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 in arr0 using binary search
size_t i0 = -1;//not found
{
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
while (i0 > low && arr0[i0-1] == arr1) {
--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;```

}