파이썬 while문 질문있습니다.

Question

파이썬 while문 질문있습니다.

조회수 774회

python

while-loop

0

싫어요

def binary_search(array, goal):
    low = 0
    high = len(array) - 1

    while low <= high:
        mid = (low + high) // 2
        if goal > array[mid]:
            low = mid + 1
        elif goal < array[mid]:
            high = mid - 1
        else:
            return mid

    return None

my_list = [1,3,5,7,9]
print(binary_search(my_list, 3))
print(binary_search(my_list, 13))

출력결과는 1 None

인데

여기서 while문 안에 있는 mid = (low+high) //2를 아래의 코드처럼

def binary_search(array, goal):
    low = 0
    high = len(array) - 1
    mid = (low + high) // 2

    while low <= high:    
        if goal > array[mid]:
            low = mid + 1
        elif goal < array[mid]:
            high = mid - 1
        else:
            return mid

    return None

my_list = [1,3,5,7,9]
print(binary_search(my_list, 3))
print(binary_search(my_list, 13))

while문 밖으로 옮기면 왜 실행이 안되나요? while문 안에있든 밖에 있든 상관없지 않나요?

히데짱 20 points

2018-08-03 11:18:57에 작성됨

댓글 입력

score 0 · Accepted Answer

이진 검색은 정렬되어 있는 리스트에서 자료를 검색할 때 사용됩니다. 이 때 찾으려는 값과 비교하며 검색 영역을 좁혀가면 검색합니다. 이 좁혀가는 기준이 mid 가 되기 때문에 값을 찾지 못했을 때 영역을 좁히고 비교를 위해 mid는 계속 갱신되야 합니다. 따라서 mid = (low+high) //2 는 while 문 안에 존재해야합니다.

좀더 이해하기 쉽게 단계를 밟아가면서 설명해 보면 아래와 같습니다.


1	2	3	`5`	7	9	12

3을 찾기 위해서 mid를 3로 설정합니다. array[3]의 값인 5와 3을 비교해 보니 찾으려는 값이 더 작습니다. 검색 영역을 [0]~[2]로 좁힙니다.


1	`2`	3

검색 영역이 [0]~[2]가 되었으므로, mid는 1이 됩니다. array[1]의 값인 2와 3을 비교해 보니 찾으려는 값이 더 큽니다. 검색 영역을 [2]~[2]로 좁힙니다.


		`3`

검색 영역이 [2]~[2]이 되었으므로, mid는 2이 됩니다. array[2]의 값인 3과 3을 비교해 보니 찾으려는 같습니다. 결과를 찾았습니다.

mid 위치의 값과 비교하고 영역을 좁혀가며 대상을 찾기 때무네 mid는 while 안에서 계속 갱신되어야 합니다.