선형 탐색

개요

• 순서대로 하나씩 찾는 탐색 알고리즘
• O(n) 시간복잡도가 걸립니다.
• 가장 단순한 탐색법

이진 탐색

개요

• 정렬 되어 있는 요소들을 반씩 제외하며 찾는 알고리즘
• O(log n) 시간복잡도가 걸립니다.
• Up & Down 게임과 같은 논리의 탐색법

특징

• 반드시 정렬 되어있어야 가능합니다.
• O(log n) 시간복잡도인 만큼 상당히 빠릅니다.
• 배열 or 이진 트리를 이용하여 구현합니다.

구현 방법

배열

• 중간에 요소를 추가하거나 삭제하는 경우 선형시간복잡도:O(n) 이 소요된다는 단점이 여전히 있습니다.
• 이 단점을 해결하기위해 '이진 탐색 트리'를 사용합니다.

1. [1:left, 2, 3, 4:mid, 5, 6, 7:right]
   • mid = (left + right) / 2

2. [1:left, 2:mid, 3:right, 4, 5, 6, 7]
   • right = mid - 1
   • mid = (left + right) / 2

3. [1, 2, 3:left-mid-right, 4, 5, 6, 7]
   • left = mid + 1
   • mid = (left + right) / 2
   • 탐색 종료

이진 탐색 트리

• 이진 탐색을 위한 이진 트리

• 루트를 기준으로 값들이 모여 있습니다.
  • 왼쪽 서브 트리 : 루트보다 작은 값
  • 오른쪽 서브 트리 : 루트보다 큰 값

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있습니다.
  • 'AVL 트리', '레드-블랙 트리'를 사용하여 이 문제를 해결할 수 있습니다.

JS에서의 구현

깃허브: https://github.com/HyeonWooGa/algorhithm-code-snippet