C++로 구현하는 정렬된 배열에서의 Floor(바닥) 값 찾기 알고리즘

이 문제에서는 정렬된 배열 arr[]와 정수 x가 주어지며, 배열 안에서 x의 Floor(바닥) 값을 찾는 프로그램을 작성해야 합니다.

여기서 정렬된 배열에서 x의 Floor란, 배열 arr[]에 존재하는 원소 중 x보다 작거나 같은 값 중 가장 큰 원소를 의미합니다.

문제 이해를 위한 예시

입력: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
출력: 9

설명: 위 배열에서 10보다 작거나 같은 수 중 가장 큰 값은 9입니다. 따라서 결과는 9가 됩니다.

해결 방법 1: 선형 탐색(Linear Search)

가장 간단한 방법은 배열을 처음부터 끝까지 순회하면서 조건을 만족하는 원소를 찾는 것입니다.

배열을 탐색하면서 각 원소를 확인하고, 현재 원소가 x보다 커지는 순간이 오면 그 앞의 원소가 곧 x의 Floor 값이 됩니다.

구현 예제

#include <iostream>
using namespace std;

int findFloorSortedArray(int arr[], int n, int x){
    if (x >= arr[n - 1])
        return (n-1);
    if (x < arr[0])
        return -1;
    for (int i = 1; i < n; i++)
        if (arr[i] > x)
            return (i - 1);
    return -1;
}
int main(){
    int arr[] = {2, 5, 6, 8, 9, 12, 21, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int floorIndex = findFloorSortedArray(arr, n - 1, x);
    if (floorIndex == -1)
        cout<<"The floor of "<<x<<" doesn't exist in the array";
    else
        cout<<"The floor of "<<x<<" in the array is "<<arr[floorIndex];
    return 0;
}

실행 결과

The floor of 10 in the array is 9

이 방법의 시간 복잡도는 O(n)으로, 배열의 모든 원소를 순차적으로 확인해야 하므로 데이터 크기가 클 경우 비효율적일 수 있습니다.

해결 방법 2: 이진 탐색(Binary Search) 활용

배열이 이미 정렬되어 있고 특정 값을 찾는 작업이므로, 이진 탐색 알고리즘을 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다.

이진 탐색 방식의 동작 과정은 다음과 같습니다.

1. 배열의 중간 인덱스에 있는 원소를 확인합니다.
2. 중간 원소와 x를 비교하여, x가 더 작으면 배열의 전반부(작은 쪽 절반)를, x가 더 크면 후반부(큰 쪽 절반)를 탐색 대상으로 좁혀 나갑니다.
3. x가 정확히 중간 원소와 일치하거나, x가 중간 원소 미만이면서 바로 앞 원소 이상인 지점을 찾으면 해당 위치가 Floor 값의 인덱스입니다.
4. 탐색 범위가 소진되거나 원소를 찾을 때까지 이 과정을 반복합니다.

구현 예제

#include <iostream>
using namespace std;

int findFloorSortedArray(int arr[], int start, int end, int x){
    if (start > end)
        return -1;
    if (x >= arr[end])
        return end;
    int mid = (start + end) / 2;
    if (arr[mid] == x)
        return mid;
    if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
        return mid - 1;
    if (x < arr[mid])
        return findFloorSortedArray(arr, start, mid - 1, x);
    return findFloorSortedArray(arr, mid + 1, end, x);
}
int main(){
    int arr[] = {2, 5, 6, 8, 9, 12, 21, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int floorIndex = findFloorSortedArray(arr, 0, n - 1, x);
    if (floorIndex == -1)
        cout<<"The floor of "<<x<<" doesn't exist in the array";
    else
        cout<<"The floor of "<<x<<" in the array is "<<arr[floorIndex];
    return 0;
}

실행 결과

The floor of 10 in the array is 9

두 방법의 성능 비교

배열이 정렬되어 있다는 전제 조건이 주어졌기 때문에, 이진 탐색을 사용하는 두 번째 방법이 선형 탐색보다 월등히 빠른 성능을 보장합니다. 따라서 실무에서는 이진 탐색 기반의 해결책을 사용하는 것이 좋습니다.