이분 탐색 or 이진 탐색 이란?

• 이분 탐색(이진 탐색)은 정렬되어 있는 배열에서 사용 가능한 알고리즘입니다.

• 그 방법은 배열에서 탐색 범위를 절반씩 나눠가면서 원하는 데이터를 탐색하는 방법입니다.

• 보통 low, mid, high를 이용해서 탐색합니다. 완전 탐색처럼 배열의 모든 원소를 비교하는 것이 아니라 low와 high의 합의 반절인 mid와 비교해나가는 것이 핵심입니다.

파이썬에서 이분탐색 코드

재귀 함수를 이용한 이분 탐색

def binarysearch(array, target, low, high):
    if high > low:
        return None
    mid = (high + low) // 2
    
    # 찾던 값을 찾은 경우 인덱스 반환
    if array[mid] == target:
        return mid 
    # 찾던 값이 중간값보다 작은 경우 high 값을 조정해서 절반 확인
    elif array[mid] > target:
        return binarysearch(array, target, low, mid - 1)
    # 찾던 값이 중간값보다 큰 경우 low 값을 조정해서 절반 확인
    else :
        return binarysearch(array, target, mid + 1, high)
    
    # 재귀적으로 이분탐색을 구현

재귀가 무엇인지는 이후에 글을 써서 자세하게 다뤄보도록 하겠습니다.
일단은 재귀는 함수가 자기 자신을 자신의 내부에서 사용하는 방식이라고 이해하면 될 것 같습니다.
위의 코드에서는 binarysearch가 함수 내부에서 자기 자신을 불렀기 때문에 재귀적이라고 할 수 있습니다. while이 없어도 함수가 함수를 부르고 함수가 함수를 부르기에 반복이 가능합니다.

반복문을 이용한 이분 탐색

def binarysearch(array, target, low, high):
    
    while low <= high:
        mid = (high + low) // 2
        
        #찾던 값을 찾은 경우 인덱스 반환
        if array[mid] == target:
            return mid
        
        #찾던 값이 중간값보다 작은 경우 high 값을 조정해서 절반 확인
        elif array[mid] > target:
            high = mid - 1
        
        #찾던 값이 중간값보다 작은 경우 low 값을 조절해서 절반 확인
        else :
            low  = mid + 1
        
    
    return None

재귀로 짜여진 코드를 반복문으로 바꾸면 이러한 형태가 됩니다. 코드에서 말하고자 하는 내용은 같고 주석으로 같은 의미인 부분을 써놨기 때문에 이해에 도움이 될 것이라고 생각합니다.

시간 복잡도

• 이분탐색의 시간 복잡도는 O(logN) 입니다.

  예를들어서 16개로 시작을 한다면 다음에는 8개 다음에는 4개 다음에는 2개를 보면서 logN개만 확인하면 되기 때문입니다. 확실히 완전탐색보다 빠를 수 밖에 없습니다.

단점은 정렬된 배열에서만 사용가능하다는 점입니다.

이분탐색을 이용하는 문제를 풀어보고 싶으시다면 제가 풀어본 내에서는

백준 1654번 랜선자르기 https://www.acmicpc.net/problem/1654
백준 2805번 나무자르기 https://www.acmicpc.net/problem/2805
백준 1920번 수 찾기 https://www.acmicpc.net/problem/1920
가 있습니다.

링크는 제가 만약 해당 알고리즘을 이용해서 푸는 문제가 있다면 추가하도록 하겠습니다.