Tìm floor của X trong mảng đã sắp xếp bằng C++

Mô tả bài toán

Cho mảng đã sắp xếp và X. Tìm phần tử lớn nhất ≤ X (floor). Trả về -1 nếu không tồn tại.

Ví dụ

arr={2,5,6,8,9,12,21,25}, X=10 → Output: 9.

Giải thuật

• Tuyến tính O(N): Duyệt tìm arr[i] > X, trả về arr[i-1].
• Binary Search O(log N): Tìm rightmost phần tử ≤ X.

Mã nguồn C++ (Binary Search)

#include <iostream>
using namespace std;

int findFloorSortedArray(int arr[], int l, int r, int x) {
    if (l > r) return -1;
    if (x >= arr[r]) return r;
    int mid = (l+r)/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, l, mid-1, x);
    return findFloorSortedArray(arr, mid+1, r, x);
}

int main() {
    int arr[] = {2,5,6,8,9,12,21,25};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 10;
    int idx = findFloorSortedArray(arr, 0, n-1, x);
    if (idx==-1) cout << "Floor doesn't exist";
    else cout << "Floor of " << x << " is " << arr[idx];
    return 0;
}

Đầu ra

The floor of 10 in the array is 9