탐색이란 의미를 잘 살펴보자. 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] ..

우리가 늘상 사용하는 index(list, data)는 과연 어떤 원리로 동작하는 것일까?기본적으로 어떠한 리스트에서 데이터의 위치를 찾는 것을 목표로 동작해야한다. 즉, 데이터의 값이 어디있는지 찾고, 그 값의 인덱스를 리턴해주어야 한다. 우리는 보통 무언가를 찾을 때 처음부터 쭈욱~ 찾아보거나 어떤 기준을 잡고 살펴보기 시작한다.한 뭉텅이씩 눈에 들어오는 양만큼 그룹을 묶어서 찾는다거나, 절반을 먼저보고 나머지를 본다거나... 컴퓨터도 똑같이 리스트에서 데이터를 찾을 때, 처음부터 쭉 살펴보거나 어떠한 기준을 가지고 리스트를 살펴보기 시작한다. 가장 기본적인 탐색 방법으로 선형 탐색과 이진 탐색에 대해서 살펴보자. 선형 탐색선형 탐색은 말 그대로 리스트를 linear하게 살펴보면서 데이터의 위치를 찾..