[알고리즘/C언어] 순차 탐색(Linear Search) vs 이진 탐색(Binary Search) 개념과 차이점 완전 정리

컴퓨터공학과 자료구조/알고리즘 중간·기말고사나 C언어 실기 시험에서 "원하는 데이터를 찾는 탐색(Search) 알고리즘"에 대해 물어볼 때 가장 먼저 등장하는 기본 개념이 있습니다. 바로 순차 탐색(Linear Search)과 이진 탐색(Binary Search)입니다.

"단순히 처음부터 찾으면 되는 거 아닌가?"

"왜 이진 탐색을 사용하기 전에는 반드시 '정렬'이 되어 있어야 할까?"

두 알고리즘의 동작 원리부터 시간 복잡도, C언어 구현 코드, 그리고 시험 단골 문제 유형까지 완벽하게 정리해 드립니다!

1. 순차 탐색(Linear Search)이란?

순차 탐색(선형 탐색)은 리스트의 첫 번째 데이터부터 마지막 데이터까지 순서대로 하나씩 비교해가며 원하는 값을 찾는 가장 직관적이고 단순한 알고리즘입니다.

🔹 특징 및 동작 방식

• 전제 조건 없음: 데이터가 정렬되어 있든 않든 상관없이 바로 사용할 수 있습니다.
• 작동 원리: Index 0부터 시작하여 찾고자 하는 값(Target)과 같은지 비교하고, 같으면 종료, 다르면 다음 인덱스로 이동합니다.
• 시간 복잡도:
  • 최선의 경우 (Best): $O(1)$ (첫 번째에 바로 찾을 때)
  • 최악의 경우 (Worst): $O(N)$ (맨 마지막에 있거나 데이터가 없을 때)

2. 이진 탐색(Binary Search)이란?

이진 탐색(이분 탐색)은 "정렬된 배열"에서 찾고자 하는 값과 중앙값(Mid)을 비교하여 탐색 범위를 반씩 줄여가며 데이터를 찾는 고속 탐색 알고리즘입니다.

⚠️ 시험 필수 강조 포인트!

이진 탐색을 수행하기 위한 대전제 조건은 **"배열 내의 데이터가 반드시 미리 정렬(Sorted)되어 있어야 한다"**는 점입니다. 정렬되어 있지 않다면 이진 탐색을 사용할 수 없습니다.

🔹 이진 탐색의 동작 단계

1. 배열의 시작 인덱스(low)와 끝 인덱스(high)를 바탕으로 중간 인덱스(mid = (low + high) / 2)를 계산합니다.
2. mid 위치의 값과 찾고자 하는 target 값을 비교합니다.
   • arr[mid] == target: 탐색 성공!
   • arr[mid] > target: 찾을 값이 중앙값보다 작으므로 오른쪽 영역을 제외 (high = mid - 1)
   • arr[mid] < target: 찾을 값이 중앙값보다 크므로 왼쪽 영역을 제외 (low = mid + 1)
3. low > high가 될 때까지 1~2 과정을 반복합니다.

3. 한눈에 비교하는 핵심 차이점 (시험 서술형 단골)

구분	순차 탐색 (Linear Search)	이진 탐색 (Binary Search)
선행 조건	정렬 불필요 (무작위 데이터 가능)	반드시 정렬되어 있어야 함
탐색 방식	처음부터 끝까지 순차적으로 비교	탐색 범위를 반($1/2$)씩 분할하며 비교
평균 시간 복잡도	$O(N)$	$O(\log N)$
최악 시간 복잡도	$O(N)$	$O(\log N)$
적합한 상황	데이터 양이 적거나 정렬되지 않은 경우	대용량 정렬 데이터를 빠르게 찾을 때

4. C언어 구현 코드 비교

시험에서 손코딩(서술형)으로 자주 나오는 핵심 C언어 구현 예시입니다.

💻 순차 탐색 C언어 코드

C

 

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // 찾았을 때 인덱스 반환
        }
    }
    return -1; // 찾지 못했을 때
}

💻 이진 탐색 C언어 코드 (반복문 방식)

C

 

int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // 오버플로우 방지용 계산

        if (arr[mid] == target) {
            return mid; // 찾았을 때 인덱스 반환
        } else if (arr[mid] > target) {
            high = mid - 1; // 왼쪽 반으로 범위를 줄임
        } else {
            low = mid + 1;  // 오른쪽 반으로 범위를 줄임
        }
    }
    return -1; // 찾지 못했을 때
}

5. 시험 단골 출제 유형 체크

1. Q. 데이터가 $1,000,000$개(100만 개) 정렬되어 있을 때, 이진 탐색의 최악 비교 횟수는 약 몇 회인가?
2. 👉 $\log_2(1,000,000) \approx 20$이므로 약 20회 만에 원하는 데이터를 찾을 수 있습니다. ($O(N)$인 순차 탐색은 최악의 경우 100만 번 비교)
3. Q. 이진 탐색을 적용하기 위해 배열에 반드시 선행되어야 하는 작업은?
4. 👉 데이터의 정렬(Sorting) 작업입니다.
5. Q. 무작위로 섞여 있는 10개의 데이터에서 특정 값을 찾을 때 더 효율적인 알고리즘은?
6. 👉 데이터 양이 매우 적고 정렬되어 있지 않으므로 순차 탐색이 정렬 비용을 고려했을 때 더 효율적입니다.