탐색 - 3. 이진 탐색(Binary Search)

📌 3. 이진 탐색(Binary Search)

---

3.1 이진 탐색(Binary Search) 개념 및 필요 조건

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘입니다.
탐색 과정에서 검색 범위를 절반씩 줄여가기 때문에 O(log n)의 시간 복잡도를 가집니다.

🔹 필요 조건

• 반드시 정렬된 배열이어야 함
  → 정렬되지 않은 배열에서는 이진 탐색을 사용할 수 없음!
• 배열을 중간값 기준으로 나누어 탐색하는 방식
  → 따라서 정렬된 데이터에서만 효율적으로 작동

---

3.2 이진 탐색의 동작 원리 (중간값 기준 비교)

이진 탐색은 중간값을 기준으로 범위를 절반씩 줄이며 검색하는 방식입니다.

🔹 탐색 과정

1. 배열의 중앙값을 찾음
2. 찾는 값과 중앙값을 비교
   • 중앙값이 찾는 값보다 크면 → 왼쪽 부분 탐색
   • 중앙값이 찾는 값보다 작으면 → 오른쪽 부분 탐색
   • 일치하면 탐색 종료
3. 위 과정을 반복하여 값을 찾거나, 없으면 탐색 종료

---

🔹 예제

배열:

[ 10, 20, 30, 40, 50, 60, 70 ]

찾고자 하는 값: 40

• 1단계: 중앙값 → 30 (왼쪽은 버림, 오른쪽 탐색)
• 2단계: 중앙값 → 50 (오른쪽은 버림, 왼쪽 탐색)
• 3단계: 중앙값 → 40 (일치! 탐색 종료)

💡 탐색 범위가 절반씩 줄어들기 때문에 O(log n)의 성능을 가짐
💡 데이터가 많을수록 선형 탐색보다 훨씬 빠름

---

3.3 재귀(Recursive) vs 반복(Iterative) 방식의 구현 비교

이진 탐색은 반복문(Iterative) 또는 재귀(Recursive) 방식으로 구현할 수 있습니다.

구현 방식	장점	단점
반복문 (Iterative)	메모리 효율적 (재귀 호출 X), 코드 실행 속도 빠름	코드가 조금 더 길어질 수 있음
재귀 (Recursive)	코드가 간결하고 직관적	깊은 재귀 호출 시 스택 오버플로우 가능

---

3.4 시간 복잡도 분석 (O(log n))

경우	비교 횟수	시간 복잡도
최선 (Best Case)	단 한 번 비교 (중앙값이 찾는 값)	O(1)
최악 (Worst Case)	계속 반으로 나누며 비교	O(log n)
평균 (Average Case)	O(log n) 번 비교 후 값 찾음	O(log n)

---

🔍 실습: 이진 탐색 구현

1️⃣ 반복문 방식 (Iterative)

#include <stdio.h>

// 반복문을 이용한 이진 탐색
int binarySearchIterative(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 중앙값 인덱스 계산

        if (arr[mid] == target) {
            return mid; // 찾았으면 인덱스 반환
        }
        if (arr[mid] < target) {
            left = mid + 1; // 오른쪽 탐색
        } else {
            right = mid - 1; // 왼쪽 탐색
        }
    }
    return -1; // 찾지 못한 경우
}

int main() {
    int numbers[] = {10, 20, 30, 40, 50, 60, 70};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    int target = 40;

    int result = binarySearchIterative(numbers, size, target);

    if (result != -1) {
        printf("값 %d은(는) 인덱스 %d에 있습니다.\n", target, result);
    } else {
        printf("값 %d을(를) 찾을 수 없습니다.\n", target);
    }

    return 0;
}

📌 실행 결과

값 40은(는) 인덱스 3에 있습니다.

---

2️⃣ 재귀 함수 방식 (Recursive)

#include <stdio.h>

// 재귀를 이용한 이진 탐색
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1; // 찾지 못한 경우
    }

    int mid = left + (right - left) / 2; // 중앙값 인덱스 계산

    if (arr[mid] == target) {
        return mid; // 찾았으면 인덱스 반환
    } 
    if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, right, target); // 오른쪽 탐색
    } 
    return binarySearchRecursive(arr, left, mid - 1, target); // 왼쪽 탐색
}

int main() {
    int numbers[] = {10, 20, 30, 40, 50, 60, 70};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    int target = 40;

    int result = binarySearchRecursive(numbers, 0, size - 1, target);

    if (result != -1) {
        printf("값 %d은(는) 인덱스 %d에 있습니다.\n", target, result);
    } else {
        printf("값 %d을(를) 찾을 수 없습니다.\n", target);
    }

    return 0;
}

---

🔍 실습: qsort()를 사용하여 정렬 후 이진 탐색 적용

정렬되지 않은 배열을 qsort()로 정렬한 후 이진 탐색을 적용하는 코드입니다.

#include <stdio.h>
#include <stdlib.h>

// 비교 함수 (qsort용)
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// 이진 탐색 함수
int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int numbers[] = {50, 10, 30, 70, 20, 60, 40}; // 정렬되지 않은 배열
    int size = sizeof(numbers) / sizeof(numbers[0]);
    int target = 40;

    // 배열 정렬
    qsort(numbers, size, sizeof(int), compare);

    // 이진 탐색 실행
    int result = binarySearch(numbers, size, target);

    if (result != -1) {
        printf("값 %d은(는) 인덱스 %d에 있습니다.\n", target, result);
    } else {
        printf("값 %d을(를) 찾을 수 없습니다.\n", target);
    }

    return 0;
}

---

📌 마무리 및 정리

• 이진 탐색(Binary Search)은 정렬된 배열에서만 사용 가능
• 시간 복잡도: O(log n) (탐색 범위 절반씩 감소)
• 반복문 방식은 메모리 효율적, 재귀 방식은 코드가 직관적
• qsort()를 이용하면 정렬 후 이진 탐색 적용 가능