[LintCode] Merge Sorted Array II

Merge two given sorted integer array A and B into a new sorted integer array.

Example

A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]

Challenge

How can you optimize your algorithm if one array is very large and the other is very small?

class Solution {
public:
    /**
     * @param A and B: sorted integer array A and B.
     * @return: A new sorted integer array
     */
    int getPos(vector<int> &A, int start, int end, int target)
    {
        if(target > A[end]) return end+1;
        
        while(start<end)
        {
            int mid = (start+end)/2;
            if(A[mid] < target) start = mid + 1;
            else end = mid;
        }
        return start;
    }
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        // write your code here
        int lenA = A.size(), lenB = B.size();
        vector<int> *pLarge, *pSmall;
        if(lenA > lenB){
            pLarge = &A;
            pSmall = &B;
        }
        else{
            pLarge = &B;
            lenA = B.size();
            pSmall = &A;
            lenB = A.size();
        }
        
        int i = 0, j = 0;
        while(j<lenB){
            i = getPos(*pLarge, i, lenA-1, (*pSmall)[j]);
            pLarge->insert(pLarge->begin()+i, (*pSmall)[j++]);
            if(i == lenA) break;
            lenA++;
        }
        while(j<lenB) pLarge->push_back((*pSmall)[j++]);
        return *pLarge;
    }
};