[ Python ] 파이썬 이분 검색(Binary Search) 코드 | 순차 탐색 vs 이분 검색

 

 

이 포스팅은 구름edu 의 파이썬으로 배우는 알고리즘 강의를 기반으로 코드를 작성했음을 밝힙니다.

edu.goorm.io/learn/lecture/22654/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88

파이썬으로 배우는 알고리즘 기초 - 구름EDU

 

 

 

이분 검색(Binary Search 란?)

 

 

주어진 리스트 S와 키 x 에 대해서,

x 를 리스트의 중앙에 위치한 원소와 비교 하고 만약 같다면 알고리즘을 종료합니다.

 

만약 x 가 그 원소보다 작으면 x 는 왼쪽에 위치함을 알 수 있으므로

왼쪽 리스트에 대해 이진 탐색을 실행합니다. (재귀)

 

마찬가지로

 

만약 x 가 그 원소보다 크면 x 는 오른쪽에 위치함을 알 수 있으므로

오른쪽 리스트에 대해 이진 탐색을 실행합니다. (재귀)

 

 

나눗셈을 할 때 슬래시 두개 (//) 는 리턴 값이 정수로 딱 떨어지게 됩니다.

 

 

 

 

[ Code ]

 

 

def binary_search(n, S, x):
    low=1
    high =n
    location=0
    while(low<=high and location==0):
        mid=(low+high)//2
        if(x==S[mid]):
            location=mid
        elif(x <S[mid]):
            high=mid-1
        else:
            low = mid+1
    return location

S=[0,5,7,8,10,11,13]
x=11

location=binary_search(len(S)-1,S,x)
print('S = ',S)
print('x = ',x)
print('location = ',location)

 

 

 

 

 

 

 

 

 

 

 

 

 

순차 탐색 vs 이분 검색

 

 

입력 리스트의 조건에 따라 탐색 알고리즘을 선택해야 합니다.

이분 검색은 정렬된 리스트에서 키를 찾아야 하고,

순차 탐색은 정렬되지 않은 리스트에서 키를 찾는 것입니다.

 

 

 

 

순차 탐색 & 이분 검색 알고리즘 효율성 비교

 

리스트의 크기	순차 탐색의 비교 횟수	이분 검색의 비교 횟수
128	128	8
1024	1024	11
1048576	1048576	21

 

 

만약 검색해야하는 숫자가 리스트 상에 없다면,

순차 탐색은 크기가 n 인 리스트에서 n번의 비교를 수행해야 합니다.

이분 검색은 크기가 n 인 리스트에서 logn +1 번의 비교를 수행합니다.

 

 

따라서 리스트의 크기가 커질 수록, 이분 검색이 효율적이라는 결론이 나올 수 있습니다.

 

 

 

 

 

 

다음 포스팅은 피보나치 수열이 되겠습니다,,,

코로나 빨리 끝나고 밖에 나가서 산책하고 싶어요,,