이분 탐색/이진 탐색(Binary Search)

이분 탐색(Binary Search)

이분 탐색(이진 탐색)은 "정렬되어 있는" 데이터들을 절반씩 탐색 범위를 좁혀가며 데이터를 탐색하는 방법이다. 이분 탐색은 데이터가 정렬되어 있어야만 사용할 수 있다.

이분 탐색은 반복문과 재귀를 이용해 구현할 수 있다.

반복문을 이용한 이분 탐색

 def binSearch(arr, num):
    start, end = 0, len(arr)-1
    while start <= end:
        mid = (start+end)//2
        if arr[mid] == num:
            return mid # 찾은 경우 해당 위치 인덱스 반환
        elif arr[mid] < num:
            start = mid+1
        else:
            end = mid-1
    return -1 # 못찾은 경우 -1 반환

print(binSearch(arr,n))

재귀를 이용한 이분 탐색

def recBinSearch(arr, num, start, end):
    if start > end: return -1

    mid = (start+end)//2
    if arr[mid] == num:
        return mid
    elif arr[mid] < num:
        return recBinSearch(arr, num, mid+1, end)
    else:
        return recBinSearch(arr,num,start,mid-1)
    
print(recBinSearch(arr,n,0,len(arr)-1))

이분 탐색에서 가장 끝쪽에 있는 값 찾기

이분 탐색은 일반적으로 찾고자 하는 값을 발견한 후 바로 종료하게 된다. 그러나 만약 데이터들이 중복된 값을 허용할때 찾고자 하는 값 중 가장 왼쪽에 있는 값 or 가장 오른쪽에 있는 값을 찾고자 할 수도 있을 것이다.

반복문을 이용한, 정답 중 가장 왼쪽에 있는 값 찾기

찾고자 하는 값과 일치한 값을 발견한 경우, 원하는 방향에 따라 해당 방향에도 찾고자 하는 값이 있는지 확인한다. 만약 있다면 그 방향에 대해 다시 이분 탐색을 수행하면 된다. 아래 예는 정답 중 가장 왼쪽에 있는 값을 찾는 것이다. 오른쪽 방향에 대해서도 간단하게 수정이 가능하다.

def binSearch(arr, num):
    start, end = 0, len(arr)-1
    while start <= end:
        mid = (start+end)//2
        if arr[mid] == num: # 값 찾았을때
            # 찾는 값 중 가장 왼쪽에 있는 값 찾고 싶을때
            if mid-1 >= start and arr[mid-1] == num:
                end = mid-1
            # 현재 값이 찾는 값 중 가장 왼쪽에 있음
            else:
                return mid 
        elif arr[mid] < num:
            start = mid+1
        else:
            end = mid-1
    return -1 # 못찾은 경우 -1 반환

재귀를 이용한, 정답 중 가장 왼쪽에 있는 값 찾기

재귀의 경우도 찾고자 하는 값을 발견한 후, 왼쪽에도 찾고자 하는 값이 존재하는 경우 왼쪽 영역에 대해 다시 이분 탐색을 수행하면 된다. 오른쪽 방향에 대해서도 간단하게 수정이 가능하다.

def recBinSearch(arr, num, start, end):
    if start > end: return -1

    mid = (start+end)//2
    if arr[mid] == num:
        # 찾는 값 중 가장 왼쪽에 있는 값 찾고 싶을때
        if mid-1 >= start and arr[mid-1] == num:
            return recBinSearch(arr,num,start,mid-1)
        # 현재 값이 찾는 값 중 가장 왼쪽에 있음
        else:
            return mid
    elif arr[mid] < num:
        return recBinSearch(arr, num, mid+1, end)
    else:
        return recBinSearch(arr,num,start,mid-1)
    
print(recBinSearch(arr,n,0,len(arr)-1))

bisect 라이브러리 이용

파이썬은 bisect 라는 이분 탐색 라이브러리(모듈)을 지원한다. 이를 이용하면 찾는 값 중 가장 왼쪽 or 오른쪽에 존재하는 값의 인덱스를 알 수 있다.

bisect_left(arr, x): arr 배열(정렬된 상태)에서 x를 넣을 수 있는 가장 왼쪽 인덱스
bisect_right(arr, x) : arr 배열(정렬된 상태)에서 x를 넣을 수 있는 가장 오른쪽 인덱스

기타로, bisect_right(arr,x) - bisect_left(arr, x) 를 하면 정렬된 리스트 arr 에 있는 x 와 동일한 값의 총 개수를 알 수 있다.

from bisect import bisect_left, bisect_right

arr = [1,2,3,5,5,5,6,8,9,12,15,17]
n = int(input())

print(bisect_left(arr,5)) # 3
print(bisect_right(arr,5)) # 6
print(bisect_left(arr,5) - bisect_right(arr,5)) # 3