C ++を使用して、ソートされた配列内のkより大きい要素の数を検索します

この問題では、N個のソートされた整数値と整数kで構成される配列arr[]が与えられます。私たちのタスクは、ソートされた配列でkより大きい要素の数を見つけることです。

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

入力

arr[] = {1, 2, 5, 7, 8, 9} k = 4

出力

4

説明

Elements greater than k = 4 are
5, 7, 8, 9

ソリューションアプローチ

この問題の簡単な解決策は、0からNまでの配列でループを使用することです。次に、kより大きい最初の要素で停止します。次に、残りの値の数を数えます。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
   for(int i = 0; i < n; i++){
      if(arr[i] > k)
         return (n - i);
   }
   return -1;
}
int main(){
   int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 5;
   cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
   return 0;
}

出力

The number of elements greater than k is 5

上記のコードはうまく機能しますが、プログラムの時間計算量はO（N）のオーダーです。

もう1つのより効率的なアプローチは、バイナリ検索を使用してkより大きい要素を見つけることです。そして、より大きな要素の数を返します。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findGreaterCount(int arr[], int n, int k){
   int s = 0;
   int e = n - 1;
   int firstGreterEle = n;
   while (s <= e) {
      int mid = s + (e - s) / 2;
      if (arr[mid] > k) {
         firstGreterEle = mid;
         e = mid - 1;
      }
      else
         s = mid + 1;
   }
   return (n - firstGreterEle);
}
int main(){
   int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 5;
   cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
   return 0;
}

出力

The number of elements greater than k is 5