Searching

개념

데이터 집합에서 원하는 값(Key)을 찾는 과정.

대상 데이터는 배열, 리스트, 트리 등 다양한 형태일 수 있으며, 데이터의 정렬 여부와 분포에 따라 적절한 탐색 알고리즘을 선택한다.

---

주요 탐색 알고리즘

알고리즘	시간 복잡도	조건 / 특징
Linear Search	O(N)	정렬 필요 없음
Binary Search	O(log N)	정렬 필요
Ternary Search	O(log₃ N)	주로 Unimodal 문제
Jump Search	O(√N)	정렬 필요
Interpolation Search	평균 O(log log N)	정렬 + 균등 분포에 효과적
Fibonacci Search	O(log N)	정렬 필요
Exponential Search	O(log N)	정렬 필요, 앞쪽에 값이 있을 때 효과적

모두 추가 공간은 일반적으로 O(1)이다.

---

1. Linear Search

처음부터 끝까지 순차적으로 탐색한다.

for (int i = 0; i < N; i++)
{
    if (arr[i] == target)
        return i;
}

return -1;

• 정렬 여부와 관계없이 사용 가능
• 구현이 단순
• Time: O(N)
• Space: O(1)

---

2. Binary Search

정렬된 데이터에서 탐색 범위를 절반씩 제거한다.

[1 3 5 7 9 11 13]
       ↑
      mid

target < mid → 왼쪽 탐색
target > mid → 오른쪽 탐색

int l = 0;
int r = N - 1;

while (l <= r)
{
    int mid = l + (r - l) / 2;

    if (arr[mid] == target)
        return mid;

    if (arr[mid] < target)
        l = mid + 1;
    else
        r = mid - 1;
}

return -1;

• 정렬 필수
• 매 탐색마다 범위가 1/2로 감소
• Time: O(log N)
• Space: O(1)

---

기타 탐색

Ternary Search

범위를 3부분으로 나누어 탐색.

주로 최댓값/최솟값이 하나인 Unimodal 함수 탐색에 사용한다.

Jump Search

정렬된 배열에서 일정 크기만큼 Jump하며 탐색 범위를 찾은 뒤 선형 탐색한다.

0 → 4 → 8 → 12 → ...

보통 Jump 크기 ≈ √N.

Time: O(√N)

Interpolation Search

Binary Search처럼 항상 중앙을 보는 것이 아니라 값의 분포를 이용해 예상 위치를 계산한다.

균등하게 분포된 데이터에서 효과적이다.

• 평균: O(log log N)
• 최악: O(N)

Fibonacci Search

Fibonacci 수를 이용해 탐색 위치를 결정한다.

Time: O(log N)

Exponential Search

먼저

1 → 2 → 4 → 8 → 16 → ...

식으로 범위를 빠르게 확장하여 target이 존재할 범위를 찾고, 이후 Binary Search를 수행한다.

Time: O(log N)

---

핵심

정렬 X
└─ Linear Search → O(N)

정렬 O
├─ Binary Search → O(log N)        ← 가장 기본
├─ Jump Search → O(√N)
├─ Interpolation Search
├─ Fibonacci Search
└─ Exponential Search

Searching의 핵심은 데이터의 정렬 여부와 특성을 이용해 탐색해야 하는 범위를 얼마나 빠르게 줄이느냐이다.