Dada una array ordenada de tamaño n. Encuentra un número de elementos que son menores o iguales a un elemento dado.
Ejemplos:
Input : arr[] = {1, 2, 4, 5, 8, 10}
key = 9
Output : 5
Elements less than or equal to 9 are 1, 2,
4, 5, 8 therefore result will be 5.
Input : arr[] = {1, 2, 2, 2, 5, 7, 9}
key = 2
Output : 4
Elements less than or equal to 2 are 1, 2,
2, 2 therefore result will be 4.
Enfoque ingenuo: busque toda la array linealmente y cuente los elementos que son menores o iguales a la clave.
Complejidad temporal: O(n).
Espacio Auxiliar: O(1).
Enfoque eficiente: como se ordena toda la array, podemos usar la búsqueda binaria para encontrar el resultado.
- Caso 1 : cuando la clave está presente en la array, la última posición de la clave es el resultado.
- Caso 2 : cuando la clave no está presente en la array, ignoramos la mitad izquierda si la clave es mayor que la mitad. Si la clave es más pequeña que la mitad, ignoramos la mitad derecha. Siempre terminamos con un caso en el que la clave está presente antes del elemento central.
Implementación:
C++
// C++ program to count smaller or equal
// elements in sorted array.
#include <bits/stdc++.h>
using namespace std;
// A binary search function. It returns
// number of elements less than of equal
// to given key
int binarySearchCount(int arr[], int n, int key)
{
int left = 0, right = n;
int mid;
while (left < right) {
mid = (right + left) >> 1;
// Check if key is present in array
if (arr[mid] == key) {
// If duplicates are present it returns
// the position of last element
while (mid + 1 < n && arr[mid + 1] == key)
mid++;
break;
}
// If key is smaller, ignore right half
else if (arr[mid] > key)
right = mid;
// If key is greater, ignore left half
else
left = mid + 1;
}
// If key is not found
// in array then it will be
// before mid
while (mid > -1 && arr[mid] > key)
mid--;
// Return mid + 1 because of 0-based indexing
// of array
return mid + 1;
}
// Driver program to test binarySearchCount()
int main()
{
int arr[] = { 1, 2, 4, 5, 8, 10 };
int key = 11;
int n = sizeof(arr) / sizeof(arr[0]);
cout << binarySearchCount(arr, n, key);
return 0;
}
Java
// Java program to count smaller or equal
// elements in sorted array.
class GFG {
// A binary search function. It returns
// number of elements less than of equal
// to given key
static int binarySearchCount(int arr[], int n, int key)
{
int left = 0, right = n;
int mid = 0;
while (left < right) {
mid = (right + left) >> 1;
// Check if key is present in array
if (arr[mid] == key) {
// If duplicates are present it returns
// the position of last element
while (mid + 1 < n && arr[mid + 1] == key)
mid++;
break;
}
// If key is smaller, ignore right half
else if (arr[mid] > key)
right = mid;
// If key is greater, ignore left half
else
left = mid + 1;
}
// If key is not found in array then it will be
// before mid
while (mid > -1 && arr[mid] > key)
mid--;
// Return mid + 1 because of 0-based indexing
// of array
return mid + 1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 5, 8, 10 };
int key = 11;
int n = arr.length;
System.out.print(binarySearchCount(arr, n, key));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to # count smaller or equal # elements in sorted array. # A binary search function. # It returns # number of elements # less than of equal # to given key def binarySearchCount(arr, n, key): left = 0 right = n mid = 0 while (left < right): mid = (right + left)//2 # Check if key is present in array if (arr[mid] == key): # If duplicates are # present it returns # the position of last element while (mid + 1<n and arr[mid + 1] == key): mid+= 1 break # If key is smaller, # ignore right half elif (arr[mid] > key): right = mid # If key is greater, # ignore left half else: left = mid + 1 # If key is not found in # array then it will be # before mid while (mid > -1 and arr[mid] > key): mid-= 1 # Return mid + 1 because # of 0-based indexing # of array return mid + 1 # Driver code arr = [1, 2, 4, 5, 8, 10] key = 11 n = len(arr) print(binarySearchCount(arr, n, key)) # This code is contributed # by Anant Agarwal.
C#
// C# program to count smaller or
// equal elements in sorted array.
using System;
class GFG {
// A binary search function.
// It returns number of elements
// less than of equal to given key
static int binarySearchCount(int[] arr,
int n, int key)
{
int left = 0;
int right = n;
int mid = 0;
while (left < right) {
mid = (right + left) / 2;
// Check if key is
// present in array
if (arr[mid] == key) {
// If duplicates are present
// it returns the position
// of last element
while (mid + 1 < n && arr[mid + 1] == key)
mid++;
break;
}
// If key is smaller,
// ignore right half
else if (arr[mid] > key)
right = mid;
// If key is greater,
// ignore left half
else
left = mid + 1;
}
// If key is not found in array
// then it will be before mid
while (mid > -1 && arr[mid] > key)
mid--;
// Return mid + 1 because of
// 0-based indexing of array
return mid + 1;
}
// Driver code
static public void Main()
{
int[] arr = { 1, 2, 4, 5, 8, 10 };
int key = 11;
int n = arr.Length;
Console.Write(binarySearchCount(arr, n, key));
}
}
// This code is contributed by ajit.
PHP
<?php
// PHP program to count
// smaller or equal
// elements in sorted array.
// A binary search function.
// It returns number of
// elements less than of
// equal to given key
function binarySearchCount($arr, $n, $key)
{
$left = 0;
$right = $n;
$mid;
while ($left < $right)
{
$mid = ($right + $left) / 2;
// Check if key is
// present in array
if ($arr[$mid] == $key)
{
// If duplicates are
// present it returns
// the position of
// last element
while ($mid + 1 < $n && $arr[$mid + 1] == $key)
$mid++;
break;
}
// If key is smaller,
// ignore right half
else if ($mid > -1 && $arr[$mid] > $key)
$right = $mid;
// If key is greater,
// ignore left half
else
$left = $mid + 1;
}
// If key is not found in
// array then it will be
// before mid
while ($arr[$mid] > $key)
$mid--;
// Return mid + 1 because
// of 0-based indexing
// of array
return $mid + 1;
}
// Driver Code
$arr = array (1, 2, 4,
5, 8, 10);
$key = 11;
$n = sizeof($arr) ;
echo binarySearchCount($arr, $n, $key);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to
// count smaller or equal
// elements in sorted array.
// A binary search function. It returns
// number of elements less than of equal
// to given key
function binarySearchCount(arr, n, key)
{
let left = 0, right = n;
let mid;
while (left < right) {
mid = (right + left) >> 1;
// Check if key is present in array
if (arr[mid] == key) {
// If duplicates are
// present it returns
// the position of last element
while ((mid + 1) < n &&
arr[mid + 1] == key)
mid++;
break;
}
// If key is smaller, ignore right half
else if (arr[mid] > key)
right = mid;
// If key is greater, ignore left half
else
left = mid + 1;
}
// If key is not found
// in array then it will be
// before mid
while (mid > -1 && arr[mid] > key)
mid--;
// Return mid + 1 because of 0-based indexing
// of array
return mid + 1;
}
let arr = [ 1, 2, 4, 5, 8, 10 ];
let key = 11;
let n = arr.length;
document.write(binarySearchCount(arr, n, key));
</script>
Producción
6
Complejidad temporal: O(n).
Espacio Auxiliar: O(1).
Aunque esta solución funciona mejor en promedio, la complejidad de tiempo en el peor de los casos de esta solución sigue siendo O(n).
El programa anterior se puede implementar utilizando una búsqueda binaria más simplificada. La idea es verificar si el elemento del medio es mayor que el elemento dado, luego actualice el índice derecho como mid – 1 pero si el elemento del medio es menor o igual que la clave, actualice la respuesta como mid + 1 y el índice izquierdo como mid + 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count smaller or equal
// elements in sorted array
#include <bits/stdc++.h>
using namespace std;
// A binary search function to return
// the number of elements less than
// or equal to the given key
int binarySearchCount(int arr[], int n, int key)
{
int left = 0;
int right = n - 1;
int count = 0;
while (left <= right) {
int mid = (right + left) / 2;
// Check if middle element is
// less than or equal to key
if (arr[mid] <= key) {
// At least (mid + 1) elements are there
// whose values are less than
// or equal to key
count = mid + 1;
left = mid + 1;
}
// If key is smaller, ignore right half
else
right = mid - 1;
}
return count;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 4, 11, 11, 16 };
int key = 11;
int n = sizeof(arr) / sizeof(arr[0]);
cout << binarySearchCount(arr, n, key);
return 0;
}
Java
// Java program to count smaller or equal
import java.io.*;
class GFG
{
// A binary search function to return
// the number of elements less than
// or equal to the given key
static int binarySearchCount(int arr[],
int n, int key)
{
int left = 0;
int right = n - 1;
int count = 0;
while (left <= right)
{
int mid = (right + left) / 2;
// Check if middle element is
// less than or equal to key
if (arr[mid] <= key)
{
// At least (mid + 1) elements are there
// whose values are less than
// or equal to key
count = mid + 1;
left = mid + 1;
}
// If key is smaller, ignore right half
else
right = mid - 1;
}
return count;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 2, 4, 11, 11, 16 };
int key = 11;
int n = arr.length;
System.out.println (binarySearchCount(arr, n, key));
}
}
// The code is contributed by Sachin.
Python3
# Python3 program to count smaller or equal # elements in sorted array # A binary search function to return # the number of elements less than # or equal to the given key def binarySearchCount(arr, n, key): left = 0 right = n - 1 count = 0 while (left <= right): mid = int((right + left) / 2) # Check if middle element is # less than or equal to key if (arr[mid] <= key): # At least (mid + 1) elements are there # whose values are less than # or equal to key count = mid + 1 left = mid + 1 # If key is smaller, ignore right half else: right = mid - 1 return count # Driver code arr = [ 1, 2, 4, 11, 11, 16 ] key = 11 n = len(arr) print( binarySearchCount(arr, n, key)) # This code is contributed by Arnab Kundu
C#
// C# program to count smaller or equal
using System;
class GFG
{
// A binary search function to return
// the number of elements less than
// or equal to the given key
static int binarySearchCount(int []arr,
int n, int key)
{
int left = 0;
int right = n - 1;
int count = 0;
while (left <= right)
{
int mid = (right + left) / 2;
// Check if middle element is
// less than or equal to key
if (arr[mid] <= key)
{
// At least (mid + 1) elements are there
// whose values are less than
// or equal to key
count = mid + 1;
left = mid + 1;
}
// If key is smaller,
// ignore right half
else
right = mid - 1;
}
return count;
}
// Driver code
public static void Main (String[] args)
{
int []arr = { 1, 2, 4, 11, 11, 16 };
int key = 11;
int n = arr.Length;
Console.WriteLine(binarySearchCount(arr, n, key));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to count smaller or equal
// elements in sorted array
// A binary search function to return
// the number of elements less than
// or equal to the given key
function binarySearchCount(arr, n, key)
{
let left = 0;
let right = n - 1;
let count = 0;
while (left <= right) {
let mid = parseInt((right + left) / 2, 10);
// Check if middle element is
// less than or equal to key
if (arr[mid] <= key) {
// At least (mid + 1) elements are there
// whose values are less than
// or equal to key
count = mid + 1;
left = mid + 1;
}
// If key is smaller, ignore right half
else
right = mid - 1;
}
return count;
}
let arr = [ 1, 2, 4, 11, 11, 16 ];
let key = 11;
let n = arr.length;
document.write(binarySearchCount(arr, n, key));
// This code is contributed by rameshtravel07.
</script>
Producción
5
Complejidad temporal: O(log(n)).
Espacio Auxiliar: O(1).
Este artículo es una contribución de nuclode . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA