Search

순차탐색

• 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 데이터의 개수가 N일 때 최대 N번의 비교 연산이 필요하므로 시간 복잡도는 O(N)이다.

이진탐색

• 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘.
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정.
• 한 번 확인할 때마다 원소의 개수가 절반씩 줄어들기 때문에 시간복잡도는 O(logN)이다.

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

이진 탐색 트리

• 부모 노드보다 왼쪽 자식 노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 크다.
• 그래서 찾고자 하는 데이터에 따라 오른쪽 또는 왼쪽 노드만 방문하면 된다.