1. 이진 탐색

문제 설명 : 

 

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다.

리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

 

예를 들어,
L = [2, 3, 5, 6, 9, 11, 15]
x = 6
의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

다른 예로,
L = [2, 5, 7, 9, 11]
x = 4
로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.

 

def solution(L, x):
    
    #init
    lower = 0
    upper = len(L) - 1
    
    while(lower <= upper):
        middle = int((lower + upper) / 2)
        if L[middle] == x:
            index = middle
            return index
        elif L[middle] < x:
            lower = middle + 1
        else :
            upper = middle - 1

    return -1

 

이해하기 : 

 

이진 탐색 알고리즘은 처음 설명을 들었을 때 아주 간단한 알고리즘이라고 생각했고 구현하기 쉬워 보였다.

하지만... 모든 알고리즘에는 예외라는 게 존재하는 법 즉 , 원소가 존재하지 않을 때 저 while loop를 빠져나오는 방법을 찾느라

좀 애를 먹었다.

 

count를 사용해서  count / 2 가 되면 빠져나오는 방법도 구상해보았으나 효율성 평가에서 통과하지 못했다.

 

저기서

lower = middle & upper = middle 만 해줄 경우

lower == 1 , upper == 1 이 돼서 middle 이  (1 + 1) / 2   == 1 이 되고

그럼 다시 lower는 1 , upper 도 1 이 되기 때문에 무한루프가 된다는 것을 명심하자.

 

이해하긴 쉬우나 구현하긴 참 어려운 알고리즘 머릿속으로 원소 하나하나가 어떻게 동작되는지 연상이 되어야 하는데

아직 공부하진 얼마 되지 않아 힘들다. 그래도 재미를 느끼기 시작했으니 계속해보자.