이진탐색(python 코드)

 

"어서와! 자료구조와 알고리즘은 처음이지?" 강의의 이진탐색 실습의 코드

---

def solution(L, x):
    answer = -1
    upper = len(L)-1
    lower = 0
    while lower <= upper:
        middle = (lower+upper) //2
        if L[middle] > x:
            upper = middle-1
        elif L[middle] < x:
            lower = middle+1
        elif L[middle] == x:
            answer = middle
            break

    return answer

이 리스트는 정렬이 되어있다.
그렇기 때문에 이진탐색을 할 수 있다.
lower가 upper보다 커질 때까지 반복한다. 만약 x가 리스트에 없다면 이 while문을 끝까지 돌 것이다.(x값이 없어서 lower가 upper보다 커지면) 그럼 결국 answer에는 -1의 값이 들어간다.
그리고 lower, upper의 중간의 값이 x보다 작다면 오른쪽만, 중간의 값이 x보다 크다면 왼쪽만 보면 된다. 그래서 중간 인덱스의 값이 x보다 작으면 그 인덱스+1을, x보다 크면 그 중간 인덱스 -1을 해 준 것이다.
그리고 중간 인덱스의 리스트 값이 x와 같다면 그 인덱스를 answer에 넣어주고 while문을 빠져나간다.

 

 

오류가 있다면 말해주시면 감사하겠습니다 ^^ !

---