#349

給兩個array，找出兩者相同的elements。

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2]

要用binary search的條件就是element要排序，

所以第一步就是將兩個array排序。

然後因為回傳的element要排除duplicate，所以用set來存。

演算法就是走過nums1的所有元素，並檢查每個元素是否存在nums2中，

檢查時使用binary search。

寫完發現其實nums1可以不用排序，nums2有排序就好，

因為只有要在nums2上使用binary search。

在寫binary search時發現有個小地方要注意，

就是r應該要設成length-1，否則會發生out of bound error。

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        /*
        binary search:
        sort 2 arrays
        for each element in nums1,
            set as target
            use binary search to see if target is in nums2,
            if yes, add to a set
        */
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        Set<Integer> set = new HashSet<>();
        for(int i : nums1){
            if(binarySearch(nums2, i)){
                set.add(i);
            }
        }

        int[] ans = new int[set.size()];
        int i=0;
        for(Integer num : set){
            ans[i++] = num;
        }
        return ans;
    }

    boolean binarySearch(int[] nums, int target){
        int l = 0, r = nums.length-1;
        while(l<=r){
            int mid = (l+r)/2;
            if(nums[mid] > target){
                r = mid-1;
            }else if(nums[mid] < target){
                l = mid+1;
            }else{
                return true;
            }
        }
        return false;
    }
}