[c++] 배열과 포인터를 사용한 데이터 검색 알고리즘

14 Dec 2023

배열과 포인터는 C++ 프로그래밍에서 데이터를 효율적으로 관리하고 조작하는 데에 있어 매우 중요합니다. 이들을 사용하여 데이터를 검색하는 여러 가지 알고리즘을 구현할 수 있습니다. 이번 글에서는 배열과 포인터를 사용하여 데이터를 검색하는 몇 가지 간단한 알고리즘에 대해 알아보겠습니다.

선형 검색 (Linear Search)

선형 검색은 간단하면서도 효율적인 검색 방법 중 하나입니다. 이 알고리즘은 배열을 처음부터 끝까지 순차적으로 검색하여 원하는 데이터를 찾는 방법입니다. 여기에는 배열과 포인터를 결합하여 구현할 수 있습니다.

#include <iostream>
using namespace std;

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;  // 찾은 경우 해당 인덱스 반환
        }
    }
    return -1;  // 찾지 못한 경우 -1 반환
}

int main() {
    int data[] = {10, 20, 30, 40, 50};
    int target = 30;
    
    int result = linearSearch(data, 5, target);
    if (result != -1) {
        cout << "찾는 값의 인덱스: " << result << endl;
    } else {
        cout << "찾는 값이 배열에 없습니다." << endl;
    }
    return 0;
}

이진 검색 (Binary Search)

이진 검색은 정렬된 배열에서 원하는 데이터를 찾는 효율적인 방법입니다. 배열 중간 요소부터 시작하여 찾고자 하는 값과 비교하고, 값을 찾을 때까지 반씩 범위를 좁혀가며 검색합니다.

#include <iostream>
using namespace std;

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;  // 찾지 못한 경우 -1 반환
}

int main() {
    int data[] = {10, 20, 30, 40, 50};
    int target = 30;
    
    int result = binarySearch(data, 5, target);
    if (result != -1) {
        cout << "찾는 값의 인덱스: " << result << endl;
    } else {
        cout << "찾는 값이 배열에 없습니다." << endl;
    }
    return 0;
}

이러한 방식으로 배열과 포인터를 사용하여 데이터 검색 알고리즘을 구현할 수 있습니다. 이러한 알고리즘을 통해 데이터를 효율적으로 관리하고 검색하는 기술을 익힐 수 있습니다.

참고문헌:

https://www.geeksforgeeks.org/linear-search/
https://www.geeksforgeeks.org/binary-search/