Dada una array ordenada y un número x, cuente los elementos más pequeños que x en la array dada.
Ejemplos:
Input : arr[] = {10, 20, 30, 40, 50}
x = 45
Output : 4
There are 4 elements smaller than 45.
Input : arr[] = {10, 20, 30, 40, 50}
x = 40
Output : 3
There are 3 elements smaller than 40.
Podemos usar upper_bound() en C++ para encontrar rápidamente el resultado. Devuelve el iterador (o puntero) al primer elemento que es mayor que el número dado. Si todos los elementos son más pequeños, devuelve el tamaño de la array. Si todos los elementos son mayores que devuelve 0.
// CPP program to count smaller elements
// in an array.
#include <bits/stdc++.h>
using namespace std;
int countSmaller(int arr[], int n, int x)
{
return upper_bound(arr, arr+n, x) - arr;
}
// Driver code
int main()
{
int arr[] = { 10, 20, 30, 40, 50 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << countSmaller(arr, n, 45) << endl;
cout << countSmaller(arr, n, 55) << endl;
cout << countSmaller(arr, n, 4) << endl;
return 0;
}
Producción:
4 5 0
Complejidad de tiempo: O (Inicio de sesión n)