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）返回arr []小于或等于K的元素的计数

• 对于此类数字，将初始变量计数设为0。

• 使用for循环遍历数字数组。i = 0至i <len

• 现在，对于每个数字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）返回arr []小于或等于K的元素的计数

• 取下标为low = 0，high = len-1和mid =（low + high）/ 2; / p>

• 取变量index = -1;

• 使用while循环，直到low <= high

• 检查arr [mid]的值。如果<= k。然后index = mid。新低=中+1

• 否则，新的高=中-1。

• 在while循环的末尾，索引将是最后一个数字<= k的索引。

• 因为数组索引从0开始并且从索引0到索引的所有数字都小于k，所以返回index + 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