2021-11-20 리스트 항목 합 탐색

탐색이란 의미를 잘 살펴보자. 

0번 인덱스 1을 취했을 때, 15가 되려면 11을 선택해야 될 가능성이 존재한다.

이때 12는 15보다 작으므로 좌측 값을 늘려야한다.

 

1번 인덱스 2를 취했을 때 15가되려면 11을 선택해야 한다.

이때 13이므로 좌측 인덱스를 늘린다.

5와 11의 경우 15보다 크므로 우측 인덱스를 줄인다.

 

이런 방식으로 가다보면 값이 없는 경우는 O(n)이고 값이 있으면 탐색된다.

 

def sum_in_list(search_sum, sorted_list):
    left = 0
    right = len(sorted_list)-1
    
    for i in range(len(sorted_list)):
        if sorted_list[right] + sorted_list[left] == search_sum:
            return True
        elif sorted_list[right] + sorted_list[left] > search_sum:
            right -=1
        else:
            left += 1
    return False

 

 

2021-11-20