https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/submissions/

---

1. 이진 탐색

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for idx, num in enumerate(numbers):
            k = target - num
            start = idx + 1
            end = len(numbers) - 1
            while start <= end:
                mid = start + (end - start) // 2
                if numbers[mid] == k:
                    return [idx + 1, mid + 1]
                elif numbers[mid] < k:
                    start = mid + 1
                else:
                    end = mid - 1
                    
    # 처음 풀이                
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for idx, num in enumerate(numbers):
            k = target - num
            start = 0
            end = len(numbers) - 1
            ans = [idx+1]
            while start <= end:
                mid = start + (end - start) // 2
                if numbers[mid] == k:
                    if mid != idx:
                        ans.append(mid + 1)
                        return ans
                    else:
                        start = mid + 1
                elif numbers[mid] < k:
                    start = mid + 1
                else:
                    end = mid - 1

2. 투 포인터

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        start = 0
        end = len(numbers) - 1
        while start <= end:
            if numbers[start] + numbers[end] == target:
                return [start + 1, end + 1]
            elif numbers[start] + numbers[end] > target:
                end -= 1
            else:
                start += 1

3. bisect_left

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for idx, num in enumerate(numbers):
            k = target - num
            i = bisect_left(numbers, k, idx + 1)
            if i < len(numbers) and numbers[i] == k:
                return [idx + 1, i + 1]

---

투 포인터 풀이가 가장 마음에 든다.