C++でソートされた配列内の小さい要素または等しい要素の数

整数の配列が与えられます。目標は、指定された値K以下の配列の要素の数を見つけることです。

入力

Arr[]= { 1, 2, 3, 14, 50, 69, 90 } K=12

出力

Numbers smaller or equal to K: 3

説明

Numbers 1,2,3 is smaller or equal to 12.

入力

Arr[]= { 12, 13, 13, 13, 14, 50, 54, 100 } K=14

出力

Numbers smaller or equal to K: 5

説明

Numbers 12, 13, 14 are smaller or equal to 14.

ナイーブアプローチ

以下のプログラムで使用されているアプローチは次のとおりです

• 整数配列Arr[]とKを取ります。

• 関数smallorEqual（int arr []、int k、int len）は、K

  以下のarr[]の要素の数を返します。

• このような数値の場合、初期変数カウントを0とします。

• forループを使用して数値の配列をトラバースします。 i=0からi

• ここで、arr [i]ごとに、<=kの場合、カウントをインクリメントします。

• 終了時に、ループカウントは条件を満たす総数になります。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int smallorEqual(int arr[],int k,int len){
   int count = 0;
   for (int i = 0; i < len; i++){
      if(arr[i]<=k)
         { count++; }
      else
         { break; }
   }
   return count;
}
int main(){
   int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
   int K = 21;
   int Length= sizeof(Arr)/sizeof(Arr[0]);
   cout <<"Numbers smaller or equal to K: "<<smallorEqual(Arr,K,Length);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Numbers smaller or equal to K: 6

効率的なアプローチ（二分探索を使用）

以下のプログラムで使用されているアプローチは次のとおりです

• 整数配列Arr[]とKを取ります。

• 関数binarySearch（int arr []、int k、int len）は、K

  以下のarr[]の要素の数を返します。

• インデックスをlow=0、high =len-1、mid =（low + high）/ 2; / p>

  とします。

• 変数index=-1;

  を取る

• whileループを使用して、low <=high

  まで

• arr[mid]の値を確認してください。 <=kの場合。次に、index=midです。新しいlow=mid + 1

• それ以外の場合は、新しいhigh=mid-1。

• whileループのインデックスの最後に、最後の番号のインデックスが作成されます<=k。

• 配列のインデックス付けは0から始まり、インデックス0からインデックスまでのすべての数値がk未満であるため、結果としてインデックス+1を返します。

例

#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[],int k,int len){
   int low = 0;
   int high = len -1;
   int mid = (high+low)/2;
   int index = -1;
   while(low <= high){
      mid =( low + high ) / 2;
      if(arr[mid] <= k){
         index = mid;
         low = mid+1;
      }
      else{
         high=mid-1;
      }
   }
   return (index+1);
}
int main(){
   int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
   int K = 21;
   int Length= sizeof(Arr)/sizeof(Arr[0]);
   cout <<"Numbers smaller or equal to K: "<<binarySearch(Arr,K,Length);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Numbers smaller or equal to K: 6