이진탐색 알고리즘

이진탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 한다.

정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능하다.

이진탐색 알고리즘이 무엇인지는, 다른 자료들을 통해 이미 충분히 많이 설명되어 있으므로 설명을 생략한다.

 

사용한 언어는 python이고 재귀를 사용한 방법, if-else문을 사용한 방법 두 가지를 모두 살펴보자.

문제는 찾고자 하는 원소 element가 리스트 안에 존재하면 그 원소의 인덱스를 리턴하고, 없으면 None을 리턴하는 것이다.

1. 재귀

def binary_search(element, lst):
    mid = len(lst)//2
    if not len(lst):
        return None
    elif element == lst[mid]:
        return mid
    elif element < lst[mid]:
        return binary_search(element, lst[:mid])
    else:
        return mid+binary_search(element, lst[mid:])
# 테스트 코드
print(binary_search(2, [2, 3, 5, 6, 7, 10, 11, 13]))
print(binary_search(0, [2, 3, 5, 6, 7, 10, 11, 13]))
print(binary_search(5, [2, 3, 5, 6, 7, 10, 11, 13]))
print(binary_search(3, [2, 3, 5, 6, 7, 10, 11, 13]))
print(binary_search(11, [2, 3, 5, 6, 7, 10, 11, 13]))

Recursion을 이용한 문제를 풀 때는 base case를 가장 먼저 생각해야 한다.

그걸 생각하기 어렵다면 먼저, recursive case를 생각한다.

이게 뭐냐면, 같은 형태이지만 더 작은 크기의 상황이라고 생각하면 된다.

후자의 상황이 반복되다가 더 작아질 수 없는 단위의 상황이 오면 그게 전자인 base case인 것이다.

그리고 이런 반복적인 부분을 제외한 탈출조건을 따로 적어줘야 할 때도 있다.

크게 보면 이게 전부이고, 문제를 여러 번 풀어서 적응해보자. 연습ㄱㄱ!!

이 문제에서는 

찾으려는 숫자가 리스트에 없는 경우와 찾으려는 숫자를 찾았을 때 멈춰야 한다.

그러기 위한 부분이 위의  if not len(lst):,  elif element == lst[mid]: 이 부분들이다.

저 코드에서 mid는 가운데 인덱스를 나타내는데, 리스트의 앞 절반 또는 뒤 절반으로 줄여 가면서 탐색해야하므로 그에 맞게 리스트 slicing을 사용하려 case분류를 해줬다.

주의할 점은, 리스트의 앞부분을 재탐색할때는 괜찮지만 리스트의 뒤 절반 부분을 재탐색할때는, 새로 호출된 함수의 인자로 들어온 리스트에서 탐색하는 거니까 인덱스가 다시 0부터 시작한다는 것이다.

그렇지만 나는 원래 리스트에서의 원소의 인덱스를 반환받길 원하므로, return을 할때 mid를 더해준다.

 

추가 설명을 덧붙이자면) 새로 호출된 함수의 인자 중 리스트에서 인덱스가 0인 원소는 바로 이전에 호출되었을 때는 인덱스가 mid였을 것이다. 따라서 새로 호출된 리스트에서 찾은 원소의 인덱스에 mid를 더해주면 이전에 호출된 인덱스를 반영할 수 있게 된다.

2. if-else

def binary_search(element, lst):
    start_idx = 0
    end_idx = len(lst) - 1
    
    while start_idx <= end_idx:
        mid = (start_idx + end_idx) // 2
        if lst[mid] == element:
            return mid
        elif lst[mid] > element:
            end_idx = mid - 1
        else:
            start_idx = mid + 1
    return None

# 테스트 코드
print(binary_search(2, [2, 3, 5, 6, 7, 10, 11, 13]))
print(binary_search(0, [2, 3, 5, 6, 7, 10, 11, 13]))
print(binary_search(5, [2, 3, 5, 6, 7, 10, 11, 13]))
print(binary_search(3, [2, 3, 5, 6, 7, 10, 11, 13]))
print(binary_search(11, [2, 3, 5, 6, 7, 10, 11, 13]))

이진 탐색은 탐색 범위를 반으로 줄여나가야 하므로, 탐색하는 범위의 시작, 끝 인덱스를 나타내는 변수를 생성했다.

while반복문을 통해 리스트 속에 찾고자 하는 원소가 있다면 해당 원소의 인덱스를 리턴하고, 없으면 반복문 탈출 후 None을 리턴한다.

여기에서도 반복해야할 것은

현재 탐색범위에서 중간값lst[mid]가 찾고자 하는 원소라면->mid 리턴 끝이고,

아니라면 탐색 범위를 줄여야 한다.

 

탐색 범위를 줄이기 위해서는, 정답원소와 중간값을 비교해서

중간값이 더 크다면 리스트의 앞절반부분을 봐야 하고

중간값이 더 작다면 리스트의 뒷절반부분을 봐야 한다.

 따라서 이를 코드로 작성하면 위와 같다.

 

이 반복문은 끝까지 찾아봤을때 없으면 탈출한다.

 여기서 계속 변화주는부분은 첫,끝인덱스인데, 이를 조작하면서 계속 범위를 줄여나가다 보면 두 인덱스가 엇갈리게 될 것이다. 그러므로 탈출조건은 위와 같이 써준다.