순차 탐색

💡 어느 한쪽 방향으로만 탐색할 수 있는 알고리즘으로 선형 탐색으로 부르기도 함

처음부터 끝까지 모든 요소를 검사하는 전략

def sequentialSearch(data, x):
    for i in range(len(data)):
        if x == data[i]:
            return i
    return -1

이진 탐색

💡 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

시간복잡도

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례한다.
• 시간 복잡도는 O(logN)을 보장함

def binarySearch(data, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        return binarySearch(data, target, start, mid-1)
    else:
        return binarySearch(data, target, mid+1, end)

[이것이 코딩 테스트다] 5. 이진 탐색

이진 탐색 트리 Binary Search Tree

💡 이진 탐색이 배열에만 사용이 가능한 알고리즘이다. 이진 탐색을 사용하려면 처음과 끝을 알아야 하고 데이터의 중앙요소를 접근 가능해야 하는데 링크드 리스트 같은 자료구조는 처음과 끝은 알 수 있지만 ‘중앙 요소’는 알 수 없다.

동적으로 노드를 추가하거나 제거할 수 있으면서 이진 탐색 알고리즘을 사용할 수 있도록 해주는 게 이진 탐색 트리 이다.

→ 자식은 최대 2개뿐인 노드로만 이루어진 이진트리이다.

이진 탐색 트리의 기본 연산

이진 탐색도 정렬이 되어있어야 탐색이 가능한 것 처럼 이진 탐색 트리도 이진 탐색이 가능한 상태로 정렬되어 있어야 한다

구조 측면에서 이진 탐색 트리는 → 각 노드의 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작다.

이진 탐색 트리의 문제점

트리가 한쪽으로 쏠리게 되면 검색효율이 극단적으로 떨어진다. → 레드 블랙 트리가 불균형한 트리로 해결해 줄 수 있음