数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的有序数组中的 Floor
在这个问题中，我们给定一个排序数组 arr[] 和一个整数值 x。我们的任务是创建一个程序来查找有序数组中的 Floor。
有序数组 arr 中 X 的 Floor 是数组 arr[] 中小于或等于 x 的最大元素。
让我们举个例子来理解这个问题
Input: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
Output: 9解释 - 在上面的数组中，9 是小于或等于 10 的最大数。
解决方案方法
解决该问题的一个简单方法是直接遍历数组并找到满足条件的元素。在遍历数组时，
我们将检查每个元素，如果它大于 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
另一种方法
解决该问题的另一种方法是使用二分查找算法，因为数组已排序，并且我们的任务基于查找值。在这个解决方案中，我们将搜索数组中间索引处的元素。然后根据中间元素，我们将进一步在数组的前半部分（较小部分）或后半部分（较大部分）中搜索数字。并继续这样做，直到遍历整个数组或在子数组的中间找到该元素。
示例
程序说明我们解决方案的工作原理
#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
更新于：2022年2月1日
418 次查看
广告