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（intarr[]，intk，intlen）返回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（intarr[]，intk，intlen）返回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