1. 순차탐색

특정 데이터를 찾기 위해 앞에서부터 차례대로 데이터를 확인하는 방법

시간 복잡도 - O(N)

2. 이진탐색

시작점, 끝점, 중간점을 사용하여 탐색 범위를 절반씩 좁혀가면 데이터를 탐색

데이터가 정렬되어 있는 경우 사용하며 데이터를 빠르게 탐색 가능

시간 복잡도 - O($logN$)

• 재귀함수
• 반복

<트리 자료구조>

노드와 노드의 연결

(1) 이진 탐색 트리

이진 탐색이 동작할 수 있는 효율적 탐색이 가능한 자료구조

• 크기 : 왼쪽 자식 노드 > 부모 노드 > 오른쪽 자식 노드

입력데이터가 많은 경우 input() 대신 sys.stdin.readline() 이용하기!

[2] 부품 찾기

import sys
n = int(sys.stdin.readline().rstrip())
arr1 = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(sys.stdin.readline().rstrip())
arr2 = list(map(int, sys.stdin.readline().rstrip().split()))
arr1.sort()

for i in arr2:
    s, e = 0, len(arr1) - 1
    result = "no"
    while s <= e:
        m = (s+e)//2
        if i == arr1[m]:
            result = "yes"
            break
        elif i > arr1[m]:
            s = m + 1
        else:
            e = m - 1
    print(result, end=" ")