[c] 배열의 검색 알고리즘

18 Dec 2023

c언어

배열에서 특정 원소를 찾는 검색 알고리즘은 여러 가지가 있습니다. 각 알고리즘은 다른 방식으로 동작하지만, 모두 목표하는 것은 원하는 원소를 효율적으로 찾는 것입니다.

1. 선형 검색 (Linear Search)

알고리즘

선형 검색은 배열을 처음부터 끝까지 차례대로 탐색하는 방법입니다.

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i; // 원소를 찾았을 때의 인덱스 반환
        }
    }
    return -1; // 원소를 찾지 못한 경우 -1 반환
}

시간 복잡도

선형 검색의 시간 복잡도는 O(n) 입니다.

2. 이진 검색 (Binary Search)

알고리즘

이진 검색은 배열이 정렬되어 있을 때, 중간 원소부터 시작하여 찾고자 하는 원소를 찾아 나가는 방법입니다.

int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) {
            return mid; // 원소를 찾았을 때의 인덱스 반환
        }
        if (arr[mid] > x) {
            return binarySearch(arr, l, mid - 1, x);
        }
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1; // 원소를 찾지 못한 경우 -1 반환
}

시간 복잡도

이진 검색의 시간 복잡도는 O(log n) 입니다.

결론

각각의 검색 알고리즘은 자신만의 장단점을 가지고 있으며, 상황에 따라 적합한 알고리즘을 선택하여 사용해야 합니다.

배열의 크기가 작거나 배열이 무작위로 정렬되어 있는 경우에는 선형 검색을 사용하는 것이 유리하지만, 배열이 정렬되어 있는 경우에는 이진 검색이 더 효율적입니다.

이러한 알고리즘들을 이해하고 상황에 맞게 적용함으로써 프로그램의 성능을 향상시킬 수 있습니다.