[2주차 TIL] KnockOn Bootcamp 탐색 알고리즘

💡 탐색 알고리즘이란?

어떠한 데이터 구조 안에서 원하는 데이터를 찾아내기 위한 방법을 말한다.

대표적인 탐색 알고리즘으로는 순차 탐색, 이진 탐색, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등이 있다.

---

🔎 순차 탐색(Sequential Search)

시간 복잡도 : O(n)

 

데이터 집합을 처음부터 끝까지 하나씩 비교하면서 데이터를 찾아내는 방법이다.

한쪽 방향으로만 탐색을 진행하여 선형 탐색(Linear Search)라고 부르기도 한다.

정렬이 되지 않은 데이터 집합이어도 사용 가능하다는 장점이 있지만 모든 데이터를 탐색하기 때문에 느리다는 단점이 있다.

 

순차 탐색 과정

---

🔎 이진 탐색(Binary Search)

시간 복잡도 : O(log n)

 

정렬된 데이터 집합에서 중간값과 비교하며 탐색 범위를 절반씩 줄여나가며 데이터를 찾아내는 방법이다.

한번 탐색이 진행될 때마다 탐색 범위가 줄어들기 때문에 속도가 빠르다는 장점이 있지만 반드시 정렬된 데이터 집합에서만 사용이 가능하다는 단점이 있다.

 

이진 탐색 과정