C++でソートされた配列のフロア

この問題では、ソートされた配列arr[]と整数値xが与えられます。私たちのタスクは、並べ替えられた配列の床を見つけるプログラムを作成することです。 。

並べ替えられた配列のXのフロア 配列arr[]の最大要素であり、x以下です。

問題を理解するために例を見てみましょう

Input: arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10
Output: 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