[자료구조] 탐색 알고리즘

탐색 알고리즘이란?

배열, 리스트, 트리 등의 자료구조에서 내가 원하는 데이터를 찾는 것이다.

대표적인 알고리즘으로 순차 탐색, 이진 탐색, 해시 탐색, 그래프 탐색 등이 있다.

---

순차 탐색 알고리즘

자료의 처음부터 끝까지 탐색하는 알고리즘이다. 

자료가 정렬되어 있지 않아도 사용할 수 있다.

 

시간 복잡도:

• 최악: O(n) (n은 배열의 크기)
• 최선: O(1) (처음에 찾으면)

 

#include <stdio.h>

int linear_search(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // 찾은 위치 반환
        }
    }
    return -1; // 못 찾았을 경우
}

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

    int result = linear_search(arr, size, target);

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

    return 0;
}

---

이진 탐색 알고리즘

데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

정렬된 배열이 먼저 정의되어 있어야 한다!

 

탐색 구조: 

1. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.

2. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로,

    X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.

3. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

 

시간 복잡도:

• 최악: O(log n) (매번 절반씩 줄이기 때문)

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid; // 찾음
        } else if (arr[mid] < target) {
            left = mid + 1; // 오른쪽 반 탐색
        } else {
            right = mid - 1; // 왼쪽 반 탐색
        }
    }

    return -1; // 못 찾음
}

int main() {
    int arr[] = {1, 3, 5, 7, 9}; // 정렬된 배열
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binary_search(arr, size, target);

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

    return 0;
}