两个有序数组中的交集

题目：

两个含有n个元素的有序（非降序）整形数组a和b（数组a和b中都没有重复元素），求出其共同元素

a = [0,1,2,3,4]

b = [1,3,5,7,9]

那么交集为{1,3}

解法1：很简单，依次遍历

vector<int> commonValue1(vector<int>a, vector<int> b){
    vector<int> result;
    if (a.size() < 1 || b.size() < 1)
        return result;
    int i = 0, j = 0;
    while (i < a.size() && j < b.size()){
        if (a[i] == b[j]){
            result.push_back(a[i]);
            i++;
            j++;
        }else if (a[i] > b[j]){
            j++;
        }else{
            i++;
        }
    }
    return result;
}

解法2：假设a很长，b很短，那么再这样遍历显然不是一个很好的方法。可以选择对b的每个元素都到a中二分查找。

具体而言，对b从后往前遍历，然后记录下b元素在a中查找的位置index（不管b中元素在不在）。因为a是增序，所以下次处理b的元素时，就可以缩小a中的查找范围index-1

//二分查找 返回下标地址，目标不存在则返回left

int binarySearch(vector<int> v,int size,int target){
    //int size = v.size();
    if (size < 1)
        return -1;
    int l = 0, r = size-1;
    while (l <= r){
        int m = (l + r) / 2;
        if (v[m] == target){
            return m;
        }else if (v[m] > target){
            r = m-1;
        }else{
            l = m+1;
        }
    }
    return l;
}
vector<int> commonValue2(vector<int> a, vector<int> b){
    vector<int> result;
    int index = a.size();
    for (int i = b.size()-1; i >= 0; i--){

        index = binarySearch(a,index-1,b[i]);

        if (a[index] == b[i])
            result.push_back(b[i]);
        if (index < 1)
            return result;
    }
    return result;
}