이진 탐색 알고리즘

https://koreanraichu.tistory.com/68

정렬 알고리즘

여기서 정렬 알고리즘을 왜 써야 하냐면 정렬 알고리즘으로 깔쌈하게 정렬하고 나면 이진 탐색 알고리즘으로 메다닥 찾을 수 있다고 했다.

 

예? 근데 그게 뭔데 메다닥이 됨? 을 알아보자.

---

그래서 이게 뭐 하는 알고리즘인가? 

검색 범위를 줄여나가면서 특정 대상을 찾는 알고리즘이다. 뭐 예를 들어서 찾고자 하는 균을 찾기 위해 계문강목과속종 단위로 좁혀나가는 뭐 그런거다. 박테리아 > 장내 박테리아 > 간균 > 대장균 이런 식. 근데 사실 이렇게 하면 느낌이 딱 안 온다 그죠? 좀 쉬운 예 없어요?

 

개강총회건 종강총회건 모임이건, 술이 들어가면 술게임을 하게 된다. 술게임이 좀 많긴 한데 우리 소주 뚜껑 갖고 하는 게임 있다. 업앤다운! 맞습니다. 소주 잔 뚜껑 안쪽에 있는 숫자에 근접하기 위해서 업, 다운을 통해 조금씩 범위를 좁혀가게 되고 마지막에는 숫자를 맞추게 되는 게임인데 이진 탐색 알고리즘도 비슷하다. 예를 들어서 1부터 100까지 있는 배열에서 30을 찾는다 치면

 

1. 50보다 큰가? -> 아니오 -> 50 위로 다 짤라!
2. 25보다 큰가? -> 예 -> 25 밑으로 다 짤라!
3. 37보다 큰가? -> 아니오 -> 37 위로 다 짤라!
4. 31보다 큰가? -> 아니오 -> 31 짤라!

해서 30이 나오게 된다. 뭐 심심하면 자르네 아주 

 

근데 이걸 하려면 뭘 찾으려는 배열이 '정렬되어 있어야' 가능하기 때문에 정렬 알고리즘과 콜라보레이션을 해야 한다고 하는 것.

 

뭔지 한번 보자!

재귀함수 없는 버전

a = [3, 7, 13, 18, 29, 33, 35, 37, 50, 59, 65, 76]

def binary_search(target,array):
    left = 0
    right = len(array) - 1

    while left <= right:
        middle = (left + right) // 2
        if array[middle] == target:
            index = middle + 1
            return "Your data is Here: {}".format(index)
            break
        elif array[middle] > target:
            right = middle - 1
        else: 
            left = middle + 1

print(binary_search(65,a))

위에 있는 배열(a)에서 65를 찾아달라는건데, 정답은 11이다. (인덱스는 10) 배열 보면 아시겠지만 해당 배열의 길이는 12이고, 거기서 두번째로 크그덩. 근데 일단은 배열이 정렬만 되어 있고 65가 어디 있는지는 모른다는 가정 하에 가 보자.

 

이 경우 배열의 left는 0, right는 11(맨 마지막 인덱스)이다. 그리고 배열의 가운데는 0+11 // 2니까 5가 된다. 배열의 5번 인덱스(6번째 값)은 33이고 65는 33보다 크므로 새로운 left는 5+1인 6이 된다. 6+11 // 2는 8이므로 8번째 인덱스인 50과 비교해보면, 65는 50보다 크다. 그러면 어캄? 네 left가 9가 됩니다. 그리고 9+11 // 2 하면 10인데 65가 여기 있었던거지 이제. 그래서 11이 된다.

 

재귀함수 있는 버전

a = [3, 7, 13, 18, 29, 33, 35, 37, 50, 59, 65, 76]
left = 0
right = len(a) - 1

def reculsive_binary(target, array, left, right):
    middle_index = (left + right) // 2
    middle = array[middle_index]
    print("Middle Index: {}\nMiddle No. {}".format(middle_index, middle))
    if target == middle:
        print("Founded at: {}".format(middle_index))
    elif middle > target: 
        right = middle_index - 1
        reculsive_binary(target, array, left, right)
    else: 
        left = middle_index + 1
        reculsive_binary(target, array, left, right)

reculsive_binary(65,a,left, right)

재귀함수는 나 자신을 호출하는 함수인데... 그거 빼면 크게 다를건 없음. 그... 대충 내가 라이츄 부르면 재귀함수다.

 

이걸 왜 업다운 게임에 비유했는지 아시리라 생각한다. 소주병 뚜껑에 적힌 숫자를 포함하는 1~50까지의 배열 안에서 특정 값을 찾기 위해 업/다운을 통해 범위를 좁혀가는 게 이진 탐색 알고리즘이다. 이걸 할 때 별도로 정렬을 안 하는 이유는 간단하다. 우리는 1~50까지의 '정렬된' 배열 안에 저 숫자가 있다고 가정하기 때문.