C++ 中排序数组的下限
c++server side programmingprogramming更新于 2025/5/31 9:37:17
在这个问题中，我们给出了一个排序数组 arr[] 和一个整数值 x。我们的任务是创建一个程序来查找排序数组中的下限。
排序数组 arr 中 X 的下限是数组 arr[] 中小于或等于 x 的最大元素。
让我们举一个例子来理解这个问题
输入:arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
输出:9
解释 −在上面的数组中，9 是小于或等于 10 的最大数字。
解决方法
这个问题的一个简单解决方法是直接遍历数组并找到满足条件的元素。在遍历数组时，
我们将检查每个元素，如果它大于 x，则返回前一个元素作为 x 的下限。
示例
程序来说明我们的解决方案的工作原理
#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
替代方法
解决问题的另一种方法是使用二分搜索算法，因为数组是排序的，我们的任务是基于查找值。在这个解决方案中，我们将在数组的中间索引中搜索元素。然后根据中间元素，我们将进一步搜索数组前半部分(较小的一半)或后半部分(较大的一半)中的数字。并继续此操作，直到遍历整个数组或在子数组的中间找到元素。
示例
程序说明我们的解决方案的工作原理
#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
