Trong bài toán này, chúng ta được cung cấp một mảng đã sắp xếp arr [] và một giá trị nguyên x. Nhiệm vụ của chúng ta là tạo một chương trình để tìm tầng trong một mảng đã được sắp xếp .
Tầng của X trong arr mảng được sắp xếp là phần tử lớn nhất của mảng arr [] nhỏ hơn hoặc bằng x.
Hãy lấy một ví dụ để hiểu vấn đề
Input: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
Output: 9 Giải thích - Trong mảng trên, số 9 là số lớn nhất nhỏ hơn hoặc bằng 10.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là trực tiếp duyệt qua mảng và tìm các phần tử thỏa mãn điều kiện. Trong khi duyệt qua mảng,
chúng tôi sẽ kiểm tra từng phần tử, nếu nó lớn hơn x, hãy trả về phần tử trước đó là tầng của x.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The floor of 10 in the array is 9
Phương pháp thay thế
Một phương pháp thay thế để giải quyết vấn đề là sử dụng thuật toán tìm kiếm nhị phân vì mảng được sắp xếp và nhiệm vụ của chúng ta dựa trên việc tìm kiếm các giá trị. Trong giải pháp này, chúng tôi sẽ tìm kiếm phần tử trong chỉ mục giữa của mảng. Sau đó, theo phần tử ở giữa, chúng ta sẽ tìm kiếm thêm số trong nửa đầu (nửa nhỏ hơn) hoặc nửa sau (nửa lớn hơn) của mảng. Và tiếp tục điều này cho đến khi toàn bộ mảng được duyệt qua hoặc phần tử được tìm thấy ở giữa mảng con.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The floor of 10 in the array is 9