/*
 * @lc app=leetcode id=349 lang=java
 *
 * [349] Intersection of Two Arrays
 */

// @lc code=start

import java.util.List;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> r = new ArrayList<>();
        for(int i=0; i<nums1.length; i++) {
            if(i>0 && nums1[i]==nums1[i-1]) {
                continue;
            }
            if(binarySearch(nums1[i], nums2)!=-1) {
                r.add(nums1[i]);
            }
        }
        return r.stream().mapToInt(i->i).toArray();
    }

    private int binarySearch(int target, int[] nums) {
        if(nums == null || nums.length == 0) {
            return -1;
        }
        int l = 0, r = nums.length-1, m;
        while(l <= r) {
            m = l + (r-l)/2;
            if(nums[m] == target) {
                return m;
            } else if(nums[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}
// @lc code=end