[이진탐색] Leet code 167. Two Sum II - Input Array Is Sorted

리트코드 167번
정렬된 리스트에서 두 수의 합이 target값이 되는 인덱스 반환하기

풀이1

투포인터

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i = 0
        j = len(numbers)-1

        while i < j:
            if numbers[i] + numbers[j] > target:
                j = j - 1

            elif numbers[i] + numbers[j] < target:
                i = i + 1

            else:
                return [i+1,j+1]

• 양끝에서 시작해서 합이 작으면 왼쪽 포인터 이동, 값이 크면 오른쪽 포인터 이동

풀이2

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for k, v in enumerate(numbers):
            left, right = k+1, len(numbers)-1
            expected = target - v
            
            while left <= right:
                mid = left + (right-left)//2
                
                if numbers[mid] < expected :
                    left = mid + 1
                elif numbers[mid] > expected:
                    right = mid -1
                else:
                    return k+1, mid+1

• k가 하나의 답이라고 하면 k보다 오른쪽에서 나머지 값 탐색하기
• k보다 작은곳은 이미 탐색했기 때문에 다시 탐색할 필요 없음