[c] 배열과 탐색 알고리즘

18 Dec 2023

c언어

배열은 프로그래밍에서 자주 사용되는 데이터 구조 중 하나입니다. 배열은 동일한 유형의 요소를 순서대로 저장하는데 사용됩니다. 이러한 배열에서 원소를 찾는 것은 프로그래밍에서 매우 일반적인 작업입니다.

선형 탐색 알고리즘

선형 탐색 알고리즘은 배열에서 요소를 찾기 위해 각 요소를 순차적으로 검사합니다.

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;  // 요소를 찾음
        }
    }
    return -1;  // 요소를 찾지 못함
}

이진 탐색 알고리즘

이진 탐색 알고리즘은 배열이 정렬되어 있다는 가정 하에 사용됩니다.

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;  // 요소를 찾지 못함
}

마치며

배열과 탐색 알고리즘은 프로그래밍에서 중요한 요소입니다. 효율적인 알고리즘을 선택하여 배열을 탐색함으로써 프로그램의 성능을 향상시킬 수 있습니다.

참고문헌:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.