//Runtime: 12 ms, faster than 89.15%
//Memory Usage: 9.2 MB, less than 73.59%

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> res;
        sort(nums2.begin(),nums2.end());
        for(auto a : nums1) {
            if(binarySearch(nums2,a)) {
                res.insert(a);
            }
        }
        return vector<int> (res.begin(),res.end());
    }

    bool binarySearch(vector<int> & nums,int target) {
        int left = 0,right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return true;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return false;
    }
};