탐색 알고리즘

탐색 알고리즘에는
순차탐색과 이진 탐색이 있다.

1. 순차탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용하며, 리스트 내에 많은 데이터가 있어도 시간만 충분하다면 항상 원하는 데이터를 찾아낼 수 있다.

이를 이용해 간단하게 코드로 나타내 본다면

#include <stdio.h>

int search(int arr[], int size, int key) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            return i;  // 찾으면 인덱스 반환
        }
    }
    return -1;  // 찾지 못하면 -1 반환
}

int main() {
    int arr[] = {3, 5, 2, 9, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 9;

    int result = search(arr, size, key);

    if (result != -1) {
        printf("찾은 값의 인덱스: %d", result);
    } else {
        printf("값을 찾지 못했습니다.");
    }

    return 0;
}

---

찾은 값의 인덱스: 3

소스코드를 실행하면 입력한 문자열이 몇 번째 데이터인지 출력값을 통해 알 수 있다.

따라서 데이터 개수가 N개라면? 최대 N번의 비교 연산이 필요하다. 그러므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이 된다.

2. 이진탐색

탐색 범위를 반으로 좁혀가며 데이터를 탐색

배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.

간단히 설명하자면
1. 배열의 중간 값을 확인합니다.
2. 찾고자 하는 값이 중간 값보다 크면, 배열의 오른쪽 절반을 탐색합니다. 찾고자 하는 값이 중간 값보다 작으면, 왼쪽 절반을 탐색합니다.
3. 이 과정을 반복하며 범위를 좁혀 나가다가 값을 찾으면 해당 인덱스를 반환하고, 값을 찾지 못하면 탐색을 종료합니다.

#include <stdio.h>

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

    while (low <= high) {
        int mid = (low + high) / 2;
        
        if (arr[mid] == key) {
            return mid;  // 값을 찾으면 인덱스 반환
        }
        else if (arr[mid] < key) { 
            low = mid + 1;  // 오른쪽 절반 탐색
        }
        else {
            high = mid - 1;  // 왼쪽 절반 탐색
        }
    }

    return -1;  // 값을 찾지 못하면 -1 반환
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 7;

    int result = bin_search(arr, size, key);

    if (result != -1) {
        printf("찾은 값의 인덱스: %d\n", result);
    } else {
        printf("값을 찾지 못했습니다.\n");
    }

    return 0;
}

---

찾은 값의 인덱스: 3

이진 탐색은 매번 탐색 범위를 절반으로 줄이기 때문에, 시간 복잡도는 O(log n)으로 순차 탐색(O(n))보다 훨씬 빠르다.