🚀 What I Will Learn

• 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)의 원리를 이해하기

순차 탐색(Sequential Search)이란? 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법

이진 탐색이란? 데이터 정렬 유무에 상관 없이, 가장 앞에 있는 원소부터 하나씩 확인하는 방법

---

순차 탐색(Sequential Search)과 이진 탐색(Binary Search)

1️⃣ 순차 탐색(Sequential Search)

• 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법

✔️ 순차 탐색 원리

5개의 원소를 순차적으로 탐색하며 찾았을 경우, 그 인덱스를 반환한다

---

2️⃣ 이진 탐색(Binary Search)

• 데이터 정렬 유무에 상관 없이, 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점 에서 𝑂(𝑁)의 시간 복잡도를 가진다
• 배열 내부 데이터가 이미 정렬 되어 있는 상황에서 사용 가능한 알고리즘.
• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다

✔️ 이진 탐색 원리

1) 가운데부터 탐색 시작

• 찾을 원소 37이 가운데 값인 57보다 작으므로 왼쪽 탐색
• 오른쪽 원소들은 더 이상 탐색할 필요 없음

• 같은 원리로 4개의 원소 중 가운데 값인 27과 비교. 27보다 크므로 오른쪽 탐색 시작

• 또 다시 가운데 값부터 탐색하는데, 가운데 값이 37이므로 탐색 종료

---

✨ tl;dr

• 순차 탐색은 𝑂(𝑁)의 시간 복잡도를 가진다
• 이진 탐색은 정렬이 된 상태에서만 사용 가능하며 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다