여기서 정렬 알고리즘을 왜 써야 하냐면 정렬 알고리즘으로 깔쌈하게 정렬하고 나면 이진 탐색 알고리즘으로 메다닥 찾을 수 있다고 했다.
예? 근데 그게 뭔데 메다닥이 됨? 을 알아보자.
그래서 이게 뭐 하는 알고리즘인가?
검색 범위를 줄여나가면서 특정 대상을 찾는 알고리즘이다. 뭐 예를 들어서 찾고자 하는 균을 찾기 위해 계문강목과속종 단위로 좁혀나가는 뭐 그런거다. 박테리아 > 장내 박테리아 > 간균 > 대장균 이런 식. 근데 사실 이렇게 하면 느낌이 딱 안 온다 그죠? 좀 쉬운 예 없어요?
개강총회건 종강총회건 모임이건, 술이 들어가면 술게임을 하게 된다. 술게임이 좀 많긴 한데 우리 소주 뚜껑 갖고 하는 게임 있다. 업앤다운! 맞습니다. 소주 잔 뚜껑 안쪽에 있는 숫자에 근접하기 위해서 업, 다운을 통해 조금씩 범위를 좁혀가게 되고 마지막에는 숫자를 맞추게 되는 게임인데 이진 탐색 알고리즘도 비슷하다. 예를 들어서 1부터 100까지 있는 배열에서 30을 찾는다 치면
- 50보다 큰가? -> 아니오 -> 50 위로 다 짤라!
- 25보다 큰가? -> 예 -> 25 밑으로 다 짤라!
- 37보다 큰가? -> 아니오 -> 37 위로 다 짤라!
- 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까지의 ‘정렬된’ 배열 안에 저 숫자가 있다고 가정하기 때문.
Reply