파이썬 이분탐색 알고리즘 Binary search #10

파이썬 이분탐색 알고리즘 Binary search #10

안녕하세요.

 

오늘은 파이썬 알고리즘, 이분탐색에 관해서 포스팅하도록 하겠습니다.

 

이분 탐색의 목적은 가지고 있는 자료를 둘로 나누어 탐색한다는 의미입니다. 하나하나 찾아보는 순차 탐색보다 원하는 자료를 훨씬 빨리 찾을 수 있는 장점이 있습니다.

 

우리는 일상 생활에서도 무의식 적으로 이분 탐색을 하고 있습니다. 예를 들어, 어떤 책에서 특정 페이지를 찾아보려고 할 때 가운데쯤을 펴서 페이지를 확인하겠죠? 164 페이지를 찾으려고 하는데 책을 펴보니 125 페이지면 우린 책의 뒤쪽으로 좀 더 넘길 겁니다. 그것이 바로 이분 탐색입니다.

그리고 우리가 호텔이나 아파트에서 호실을 찾을 때도 이분 탐색을 하게 됩니다. 엘리베이터가 열리고 보이는 벽에 각 방향에 있는 호실이 쓰여있는 경우를 보신 적이 있으실 겁니다. 그럼 찾고 있는 호실이 해당한 방향으로 이동을 하게 됩니다. 이것 또한 이분 탐색입니다.

 

이와 같이 우리는 이미 많은 이분 탐색의 경험이 있습니다. 그리고, 그 알고리즘을 이해하고 있는 것 이죠. 이젠 이 것을 알고리즘으로, 파이썬으로 풀어내기만 하면 이분 탐색은 끝이 나게 됩니다.

 

이젠 문제를 한번 볼까요? 이미 정렬이 된 리스트 안에서 원하는 숫자를 찾아가는 이분 탐색 문제입니다.

리스트 : [1,4,9,16,25,36,49,64,81]

찾는 값 : 36

 

1. 먼저 리스트에서 중간 위치를 찾습니다. 4번째 위치한 25가 바로 중간값 이겠네요.

 

2. 찾는 값과 중간 값을 비교합니다. 36은 중간값 25보다 큽니다. 그런 25보다 오른쪽에 위치하겠네요.

 

3. 리스트에서 25보다 오른쪽에 있는 [36,49,64,81]에서 중간값을 찾아봅니다. 짝수개가 남았기 때문에 중간보다 앞에 있는 49를 중간값으로 지정합니다.

 

4. 찾는 값 36은 중간 값인 49보다 작습니다. 그럼 왼쪽에 있겠죠.

 

5. 49보다 왼쪽에 있는 값은 36 하나뿐입니다. 그러므로 바로 36이 위치한 곳, 바로 리스트 5번의 데이터 36이 찾는 값입니다. 위치 번호 5를 리턴하면 알고리즘은 끝나게 됩니다.

 

이분 탐색 알고리즘을 소스 코드로 표현해 보겠습니다.

# 리스트에서 특정 숫자 위치 찾기(이분 탐색)
# 입력: 리스트 a, 찾는 값 x
# 출력: 찾으면 그 값의 위치, 찾지 못하면 -1

def binary_search(a, x):
    # 탐색할 범위를 저장하는 변수 start, end
    # 리스트 전체를 범위로 탐색 시작(0 ~ len(a)-1)
    start = 0
    end = len(a) - 1

    while start <= end: # 탐색할 범위가 남아 있는 동안 반복
        mid = (start + end) // 2  # 탐색 범위의 중간 위치
        if x == a[mid]:   # 발견!
            return mid
        elif x > a[mid]:  # 찾는 값이 더 크면 오른쪽으로 범위를 좁혀 계속 탐색
            start = mid + 1
        else:             # 찾는 값이 더 작으면 왼쪽으로 범위를 좁혀 계속 탐색
            end = mid - 1

    return -1  # 찾지 못했을 때

d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))
print(binary_search(d, 50))

 

이젠 이 알고리즘을 분석해 보겠습니다.

 

이분 탐색은 앞서 설명드렸다시피 찾는 값이 있을법한 범위를 절반으로 줄여가며 탐색하는 알고리즘입니다. 만약 데이터가 1만 개가 있다면 순차 탐색의 경우는 최대 1만 번의 탐색을 해야 하는 반면, 이분 탐색은 약 13~14번의 탐색이면 결과를 확인할 수 있습니다.

 

이분 탐색의 계산 복잡도는 O(logn)으로 순차 탐색의 계산 복잡도 O(n) 보다 훨씬 좋습니다. 물론 이분 탐색을 가능하게 하려면 자료를 미리 정렬해 둬야 하는 번거로움이 있지만, 어떤 리스트에서 특정값을 계속 찾아야 하는 작업이 있다면 훨씬 효율적인 방법이 될 수 있습니다.

 

우리가 이미 알고 있는 B트리 인덱스와 비슷하지 않습니까? 우리가 DB를 사용할 때 이미 효율적으로 생각하고 있던 이 B트리 인덱스와 이분 탐색에 관해서 한번 생각해보시기 바랍니다.

 

오늘 하루도 파이팅하시고!! 읽어주셔서 감사합니다.

 

 

 

# 파이썬으로 배우는 알고리즘 컨텐츠는 <모두의파이썬X알고리즘, 길벗>을 참고로 작성하는 포스팅 입니다. 물론 협찬은 없습니다.ㅎㅎ

https://book.naver.com/bookdb/book_detail.nhn?bid=14341699

 

 

by.sTricky