Dada una array ordenada y un valor x, el piso de x es el elemento más grande en una array menor o igual que x. Escribe funciones eficientes para encontrar el piso de x.
Ejemplos:
Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 5
Output : 2
2 is the largest element in
arr[] smaller than 5.
Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 20
Output : 19
19 is the largest element in
arr[] smaller than 20.
Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 0
Output : -1
Since floor doesn't exist,
output is -1.
Enfoque de método simple
: la idea es simple, recorrer la array y encontrar el primer elemento mayor que x. El elemento justo antes del elemento encontrado es el piso de x.
Algoritmo:
- Atraviesa la array de principio a fin.
- Si el elemento actual es mayor que x, imprima el número anterior y rompa el bucle.
- Si no hay un número mayor que x, imprima el último elemento
- Si el primer número es mayor que x, imprima -1
C++
// C++ program to find floor of a given number
// in a sorted array
#include <iostream>
using namespace std;
/* An inefficient function to get
index of floor of x in arr[0..n-1] */
int floorSearch(int arr[], int n, int x)
{
// If last element is smaller than x
if (x >= arr[n - 1])
return n - 1;
// If first element is greater than x
if (x < arr[0])
return -1;
// Linearly search for the first element
// greater than x
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
/* Driver program to check above functions */
int main()
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = floorSearch(arr, n - 1, x);
if (index == -1)
cout<<"Floor of "<<x <<" doesn't exist in array ";
else
cout<<"Floor of "<< x <<" is " << arr[index];
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C/C++ program to find floor of a given number
// in a sorted array
#include <stdio.h>
/* An inefficient function to get
index of floor of x in arr[0..n-1] */
int floorSearch(int arr[], int n, int x)
{
// If last element is smaller than x
if (x >= arr[n - 1])
return n - 1;
// If first element is greater than x
if (x < arr[0])
return -1;
// Linearly search for the first element
// greater than x
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
/* Driver program to check above functions */
int main()
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = floorSearch(arr, n - 1, x);
if (index == -1)
printf("Floor of %d doesn't exist in array ", x);
else
printf("Floor of %d is %d", x, arr[index]);
return 0;
}
Java
// Java program to find floor of
// a given number in a sorted array
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG {
/* An inefficient function to get index of floor
of x in arr[0..n-1] */
static int floorSearch(
int arr[], int n, int x)
{
// If last element is smaller than x
if (x >= arr[n - 1])
return n - 1;
// If first element is greater than x
if (x < arr[0])
return -1;
// Linearly search for the first element
// greater than x
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = arr.length;
int x = 7;
int index = floorSearch(arr, n - 1, x);
if (index == -1)
System.out.print(
"Floor of " + x
+ " doesn't exist in array ");
else
System.out.print(
"Floor of " + x + " is "
+ arr[index]);
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
Python3
# Python3 program to find floor of a
# given number in a sorted array
# Function to get index of floor
# of x in arr[low..high]
def floorSearch(arr, low, high, x):
# If low and high cross each other
if (low > high):
return -1
# If last element is smaller than x
if (x >= arr[high]):
return high
# Find the middle point
mid = int((low + high) / 2)
# If middle point is floor.
if (arr[mid] == x):
return mid
# If x lies between mid-1 and mid
if (mid > 0 and arr[mid-1] <= x
and x < arr[mid]):
return mid - 1
# If x is smaller than mid,
# floor must be in left half.
if (x < arr[mid]):
return floorSearch(arr, low, mid-1, x)
# If mid-1 is not floor and x is greater than
# arr[mid],
return floorSearch(arr, mid + 1, high, x)
# Driver Code
arr = [1, 2, 4, 6, 10, 12, 14]
n = len(arr)
x = 7
index = floorSearch(arr, 0, n-1, x)
if (index == -1):
print("Floor of", x, "doesn't exist \
in array ", end = "")
else:
print("Floor of", x, "is", arr[index])
# This code is contributed by Smitha Dinesh Semwal.
C#
// C# program to find floor of a given number
// in a sorted array
using System;
class GFG {
/* An inefficient function to get index of floor
of x in arr[0..n-1] */
static int floorSearch(int[] arr, int n, int x)
{
// If last element is smaller than x
if (x >= arr[n - 1])
return n - 1;
// If first element is greater than x
if (x < arr[0])
return -1;
// Linearly search for the first element
// greater than x
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
// Driver Code
static void Main()
{
int[] arr = { 1, 2, 4, 6, 10, 12, 14 };
int n = arr.Length;
int x = 7;
int index = floorSearch(arr, n - 1, x);
if (index == -1)
Console.WriteLine("Floor of " + x + " doesn't exist in array ");
else
Console.WriteLine("Floor of " + x + " is " + arr[index]);
}
}
// This code is contributed
// by mits
PHP
<?php
// PHP program to find floor of
// a given number in a sorted array
/* An inefficient function
to get index of floor
of x in arr[0..n-1] */
function floorSearch($arr, $n, $x)
{
// If last element is smaller
// than x
if ($x >= $arr[$n - 1])
return $n - 1;
// If first element is greater
// than x
if ($x < $arr[0])
return -1;
// Linearly search for the
// first element greater than x
for ($i = 1; $i < $n; $i++)
if ($arr[$i] > $x)
return ($i - 1);
return -1;
}
// Driver Code
$arr = array (1, 2, 4, 6, 10, 12, 14);
$n = sizeof($arr);
$x = 7;
$index = floorSearch($arr, $n - 1, $x);
if ($index == -1)
echo "Floor of ", $x,
"doesn't exist in array ";
else
echo "Floor of ", $x,
" is ", $arr[$index];
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to find floor of
// a given number in a sorted array
/* An inefficient function to get index of floor
of x in arr[0..n-1] */
function floorSearch(arr, n, x)
{
// If last element is smaller than x
if (x >= arr[n - 1])
return n - 1;
// If first element is greater than x
if (x < arr[0])
return -1;
// Linearly search for the first element
// greater than x
for (let i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
// Driver Code
let arr = [ 1, 2, 4, 6, 10, 12, 14 ];
let n = arr.length;
let x = 7;
let index = floorSearch(arr, n - 1, x);
if (index == -1)
document.write(
"Floor of " + x
+ " doesn't exist in array ");
else
document.write(
"Floor of " + x + " is "
+ arr[index]);
</script>
Producción:
Floor of 7 is 6.
Análisis de Complejidad:
- Complejidad temporal: O(n).
Para atravesar una array, solo se necesita un bucle, por lo que la complejidad del tiempo es O (n). - Complejidad espacial: O(1).
No se requiere espacio adicional, por lo que la complejidad del espacio es constante
Enfoque de método eficiente
: hay una trampa en el problema, la array dada está ordenada. La idea es usar la búsqueda binaria para encontrar el piso de un número x en una array ordenada comparándolo con el elemento del medio y dividiendo el espacio de búsqueda por la mitad.
Algoritmo:
- El algoritmo se puede implementar de forma recursiva o mediante iteración, pero la idea básica sigue siendo la misma.
- Hay algunos casos base para manejar.
- Si no hay un número mayor que x, imprima el último elemento
- Si el primer número es mayor que x, imprima -1
- cree tres variables bajo = 0 , medio y alto = n-1 y otra variable para almacenar la respuesta
- Ejecute un bucle o recurse hasta que, a menos que, low sea menor o igual que high.
- verifique si el elemento medio ( (bajo + alto) /2 ) es menor que x, si es así, actualice el bajo, es decir, bajo = medio + 1 , y actualice la respuesta con el elemento medio. En este paso estamos reduciendo el espacio de búsqueda a la mitad.
- De lo contrario, actualice el alto, es decir, alto = medio – 1
- Imprime la respuesta.
C++
// A C/C++ program to find floor
// of a given number in a sorted array
#include <iostream>
using namespace std;
/* Function to get index of floor of x in
arr[low..high] */
int floorSearch(int arr[], int low,
int high, int x)
{
// If low and high cross each other
if (low > high)
return -1;
// If last element is smaller than x
if (x >= arr[high])
return high;
// Find the middle point
int mid = (low + high) / 2;
// If middle point is floor.
if (arr[mid] == x)
return mid;
// If x lies between mid-1 and mid
if (mid > 0 && arr[mid - 1] <= x
&& x < arr[mid])
return mid - 1;
// If x is smaller than mid, floor
// must be in left half.
if (x < arr[mid])
return floorSearch(
arr, low, mid - 1, x);
// If mid-1 is not floor and x is
// greater than arr[mid],
return floorSearch(arr, mid + 1, high, x);
}
/* Driver program to check above functions */
int main()
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = floorSearch(arr, 0, n - 1, x);
if (index == -1)
cout<< "Floor of " <<x <<" doesn't exist in array ";
else
cout<<"Floor of "<< x <<" is " << arr[index];
return 0;
}
// this code is contributed by shivanisinghss2110
C
// A C/C++ program to find floor
// of a given number in a sorted array
#include <stdio.h>
/* Function to get index of floor of x in
arr[low..high] */
int floorSearch(int arr[], int low,
int high, int x)
{
// If low and high cross each other
if (low > high)
return -1;
// If last element is smaller than x
if (x >= arr[high])
return high;
// Find the middle point
int mid = (low + high) / 2;
// If middle point is floor.
if (arr[mid] == x)
return mid;
// If x lies between mid-1 and mid
if (mid > 0 && arr[mid - 1] <= x
&& x < arr[mid])
return mid - 1;
// If x is smaller than mid, floor
// must be in left half.
if (x < arr[mid])
return floorSearch(
arr, low, mid - 1, x);
// If mid-1 is not floor and x is
// greater than arr[mid],
return floorSearch(arr, mid + 1, high, x);
}
/* Driver program to check above functions */
int main()
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = floorSearch(arr, 0, n - 1, x);
if (index == -1)
printf(
"Floor of %d doesn't exist in array ", x);
else
printf(
"Floor of %d is %d", x, arr[index]);
return 0;
}
Java
// Java program to find floor of
// a given number in a sorted array
import java.io.*;
class GFG {
/* Function to get index of floor of x in
arr[low..high] */
static int floorSearch(
int arr[], int low,
int high, int x)
{
// If low and high cross each other
if (low > high)
return -1;
// If last element is smaller than x
if (x >= arr[high])
return high;
// Find the middle point
int mid = (low + high) / 2;
// If middle point is floor.
if (arr[mid] == x)
return mid;
// If x lies between mid-1 and mid
if (
mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
// If x is smaller than mid, floor
// must be in left half.
if (x < arr[mid])
return floorSearch(
arr, low,
mid - 1, x);
// If mid-1 is not floor and x is
// greater than arr[mid],
return floorSearch(
arr, mid + 1, high,
x);
}
/* Driver program to check above functions */
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = arr.length;
int x = 7;
int index = floorSearch(
arr, 0, n - 1,
x);
if (index == -1)
System.out.println(
"Floor of " + x + " dosen't exist in array ");
else
System.out.println(
"Floor of " + x + " is " + arr[index]);
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 program to find floor of a
# given number in a sorted array
# Function to get index of floor
# of x in arr[low..high]
def floorSearch(arr, low, high, x):
# If low and high cross each other
if (low > high):
return -1
# If last element is smaller than x
if (x >= arr[high]):
return high
# Find the middle point
mid = int((low + high) / 2)
# If middle point is floor.
if (arr[mid] == x):
return mid
# If x lies between mid-1 and mid
if (mid > 0 and arr[mid-1] <= x
and x < arr[mid]):
return mid - 1
# If x is smaller than mid,
# floor must be in left half.
if (x < arr[mid]):
return floorSearch(arr, low, mid-1, x)
# If mid-1 is not floor and x is greater than
# arr[mid],
return floorSearch(arr, mid + 1, high, x)
# Driver Code
arr = [1, 2, 4, 6, 10, 12, 14]
n = len(arr)
x = 7
index = floorSearch(arr, 0, n-1, x)
if (index == -1):
print("Floor of", x, "doesn't exist\
in array ", end = "")
else:
print("Floor of", x, "is", arr[index])
# This code is contributed by Smitha Dinesh Semwal.
C#
// C# program to find floor of
// a given number in a sorted array
using System;
class GFG {
/* Function to get index of floor of x in
arr[low..high] */
static int floorSearch(
int[] arr, int low,
int high, int x)
{
// If low and high cross each other
if (low > high)
return -1;
// If last element is smaller than x
if (x >= arr[high])
return high;
// Find the middle point
int mid = (low + high) / 2;
// If middle point is floor.
if (arr[mid] == x)
return mid;
// If x lies between mid-1 and mid
if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
// If x is smaller than mid, floor
// must be in left half.
if (x < arr[mid])
return floorSearch(arr, low,
mid - 1, x);
// If mid-1 is not floor and x is
// greater than arr[mid],
return floorSearch(arr, mid + 1, high,
x);
}
/* Driver program to check above functions */
public static void Main()
{
int[] arr = { 1, 2, 4, 6, 10, 12, 14 };
int n = arr.Length;
int x = 7;
int index = floorSearch(arr, 0, n - 1,
x);
if (index == -1)
Console.Write("Floor of " + x + " dosen't exist in array ");
else
Console.Write("Floor of " + x + " is " + arr[index]);
}
}
// This code is contributed by nitin mittal.
Javascript
<script>
// javascript program to find floor of
// a given number in a sorted array
/* Function to get index of floor of x in
arr[low..high] */
function floorSearch(
arr , low,
high , x)
{
// If low and high cross each other
if (low > high)
return -1;
// If last element is smaller than x
if (x >= arr[high])
return high;
// Find the middle point
var mid = (low + high) / 2;
// If middle point is floor.
if (arr[mid] == x)
return mid;
// If x lies between mid-1 and mid
if (
mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
// If x is smaller than mid, floor
// must be in left half.
if (x < arr[mid])
return floorSearch(
arr, low,
mid - 1, x);
// If mid-1 is not floor and x is
// greater than arr[mid],
return floorSearch(
arr, mid + 1, high,
x);
}
/* Driver program to check above functions */
var arr = [ 1, 2, 4, 6, 10, 12, 14 ];
var n = arr.length;
var x = 7;
var index = floorSearch(
arr, 0, n - 1,
x);
if (index == -1)
document.write(
"Floor of " + x + " dosen't exist in array ");
else
document.write(
"Floor of " + x + " is " + arr[index]);
// This code is contributed by Amit Katiyar
</script>
Producción:
Floor of 7 is 6.
Análisis de Complejidad:
- Complejidad temporal: O(log n).
Para ejecutar una búsqueda binaria, la complejidad de tiempo requerida es O (log n). - Complejidad espacial: O(1).
Como no se requiere espacio adicional, la complejidad del espacio es constante.
Este artículo es una contribución de Mayank Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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