탐색 알고리즘 (Search Algorithm)

선형 탐색(Linear Search)

- 리스트 안에 있는 데이터들을 맨 앞이나 맨 뒤에서부터 순서대로 탐색하는 알고리즘

- 시간 복잡도 O(N)

 

이진 탐색(Binary Search)

- 리스트 안에 있는 데이터들을 중간 지점을 기준으로 데이터를 반씩 나눠서 탐색하는 알고리즘

- 원하는 값을 찾을 때까지 반을 나눈 후 탐색하는 과정을 반복함

- 시간 복잡도 O(logN)

 

이진 탐색 트리(BST, Binary Search Tree)

- 각 노드가 최대 두개의 자식을 갖는 탐색 트리이며 왼쪽 자식 트리에는 부모의 키 보다 작은 값을 오른쪽 자식 트리에는 부모의 키 보다 큰 값을 포함하는 속성을 가짐

- 시간 복잡도 O(H) (H = 트리의 높이)