이진 탐색

배열 내부의 데이터가 정렬되어 있을 때 O(logN)의 시간 복잡도로 원하는 값을 찾을 수 있는 이진 탐색에 대해 알아보자.

 

이진 탐색(Binary Search)

이진 탐색은 배열 내부의 데이터가 정렬되어 있는 경우에만 사용할 수 있는 알고리즘이다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.

 

이진 탐색에서는 시작점, 중간점, 끝점으로 3개의 변수를 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복해서 비교해서 원하는 데이터를 찾는다는 컨셉이다.

 

대충 이런 느낌이다. 코드를 살펴보면 이해가 될 것이다.

def binary_search(arr, target, start, end):
    if start > end:
        return None
    mid = (start+end)//2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr,target,start,mid-1)
    else:
        return binary_search(arr,target,mid+1,end)

#입력
n, target = list(map(int,input().split()))
arr = list(map(int,input().split()))

#메인 부분
result = binary_search(arr, target, 0, n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

 

이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어들기 때문에 O(logN)의 시간 복잡도를 가진다. 절반씩 데이터를 줄어들도록 만든다는 점에서 퀵 정렬과 공통점이 있다.

 

 

이진 탐색 트리

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 형태로 항상 데이터가 정렬되어 있다.

데이터베이스뿐만 아니라 큰 데이터를 처리하는 소프트웨어 대부분이 데이터를 트리로 저장해서 이진 탐색과 같은 탐색 기법으로 빠르게 탐색한다.

 

이진 탐색 트리는 leftchild < parent < rightchild 가 성립하는 트리이다. 언제나 이 크기 순서로 트리가 연결이 되어있기 때문에 원하는 값을 찾으려고 할 때 root값부터 찾으려는 target값을 비교해서 left 혹은 right로 내려가기만 하면 된다.