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

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 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[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;

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注