class Solution(object):
 def intersection(self, nums1, nums2):
 nums1 = set(nums1)
 nums2 = set(nums2)
 res = []
 
 for num in nums1:
 if num in nums2:
 res.append(num)
 return res

class Solution(object):
 def intersect(self, nums1, nums2):
 nums1.sort()
 nums2.sort()
 
 i, j = 0, 0
 m, n = len(nums1), len(nums2)
 res = []
 
 while i < m and j < n:
 if nums1[i] == nums2[j]:
 res.append(nums1[i])
 i += 1; j += 1
 elif nums1[i] < nums2[j]:
 i += 1
 else:
 j += 1
 return res

class Solution(object):
 def intersect(self, nums1, nums2):
 nums1.sort()
 nums2.sort()
 
 if len(nums1) < len(nums2):
 shortNums = nums1 ; longNums = nums2
 else:
 shortNums = nums2 ; longNums = nums1
 
 res = []
 left, right = 0, len(longNums)
 for ele in shortNums:
 index = self.binarySearch(longNums, res, left, right, ele)
 if index != -1:
 left = index + 1
 res.append(longNums[index])
 return res
 
 def binarySearch(self, longNums, res, left, right, target):
 while left + 1 < right:
 mid = (left + right) // 2
 if longNums[mid] == target:
 right = mid
 elif longNums[mid] < target:
 left = mid
 else:
 right = mid
 
 if left < len(longNums) and longNums[left] == target:
 return left
 if right < len(longNums) and longNums[right] == target:
 return right
 return -1