資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告