## 題解

### 二分搜索

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # Time complexity: O(nlogn)
        # Space complexity: O(1)
        n = len(numbers)
        def binary_search(nums: List[int], t: int, curr: int):
            nonlocal n
            left, right = 0, n - 1
            while left <= right:
                mid = left + (right - left) // 2
                if mid == curr:
                    left = mid + 1
                    continue
                if nums[mid] < t:
                    left = mid + 1
                elif nums[mid] > t:
                    right = mid - 1
                else:
                    return mid
            return -1

        for i in range(n):
            num = numbers[i]
            t = target - num
            mid = binary_search(numbers,t,i)
            if mid != -1:
                return [i+1,mid+1]