탐색 알고리즘(순차, 이진, 이진 탐색 트리, 해시 탐색)

1. 순차 탐색 (Sequential Search)

- 순차적으로 하나씩 비교

- 따라서 입력 값 만큼 비교가 이루어짐 O(n)

2. 이진 탐색(Binary Search)

- 정렬된 데이터를 반씩 쪼개서 데이터가 들어있는 쪽을 재귀함수를 이용해 다시 검색

- 분할 정복 알고리즘으로 문제가 1/2으로 감소하기 때문에 O(logn)이 된다.

3. 이진 탐색 트리 (Binary Search Tree)

- 이진 탐색을 적용한 이진 트리.

- 하나의 노드는 0-2개의 자식 노드를 갖을 수 있으며, 자식 노드 중 왼쪽에는 작은 값, 오른쪽에는 큰 값이 온다. 

- 한쪽으로 치우져친 (사향 트리) 트리의 경우 최악의 시간 복잡도를 갖는다. O(n)

- 평균적으로 O(logn)의 시간 복잡도를 갖는다.