<aside> 📖 Contents

</aside>

⚫️ 탐색(검색) 알고리즘

• 순차탐색 (선형탐색)
  • 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 떼이터를 하나씩 확인하는 방법
  • 보통 정렬되지 않은 데이터들에서 원하는 값을 찾을 때 사용된다.
  • 순차 탐색의 경우 N번의 탐색을 무조건 진행해야하기 때문에 최선/최악의 경우 시간복잡도 O(N)을 갖는다.
• 이진탐색
  • 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좆ㅂ혀가며 데이터를 탐색하는 방법
  • 이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
  • 탐색범위를 절반씩 줄여나가기 때문에 log 시간의 시간복잡도를 보장받을 수 있다.

▪️ 이진탐색 동작 방식

1️⃣ 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보자.

2️⃣ 시작점은 0, 끝점은 9, 중간점 4로 설정 가능 (index)

보통 중간점이 두개 존재하는 경우, 중간점 인덱스 값에서 소수점 이하는 제거하고 중간점을 찾는다.

찾고자 하는 값, 4와 비교해서 중간점위치의 값이 더 크다면, 중간점을 포함한 오른쪽에 있는 값들은 확인하지 않고 넘어간다. 여기의 경우 지금 우리가 찾고자하는 값 4보다 중간점 8이 더 크기때문에 더 작은 부분만 탐색을 다시 시작한다.

3️⃣ 시작점 0, 끝점 3, 중간점 1

지금은 중간점 값인 2보다 우리가 찾고자하는 값이 더 크기 때문에, 우리는 중간점을 포함해서 왼쪽을 모두 버린다.

4️⃣ 시작점 2, 끝점 3, 중간점 2

중간점 위치의 4가 우리가 찾고자하는 값과 동일하기 때문에 탐색을 멈춘다. 이로써 우리가 찾고자하는 값은 index 2의 위치에 존재한다고 알 수 있다.

이렇게 우리는, 우리가 찾고자하는 값의 위치나, 존재여부를 확인 가능하다.

▪️ 이진 탐색의 시간복잡도 → O(logN)