## 題解

### Binary Search

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        def binary_search(nums: List[int],target: int):
            n = len(nums)
            left, right = 0, n - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    return mid
            return -1

        output = []
        if len(nums1) > len(nums2):
            nums1 = sorted(nums1)
            n1 = nums1
            n2 = nums2
        else:
            nums2 = sorted(nums2)
            n1 = nums2
            n2 = nums1
        for num in n2:
            search = binary_search(n1,num)
            if search != -1:
                output.append(n1[search])
                n1[search] = -1
                n1 = sorted(n1)
        return output