Piso en una array ordenada

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: 
 

  1. Atraviesa la array de principio a fin.
  2. Si el elemento actual es mayor que x, imprima el número anterior y rompa el bucle.
  3. Si no hay un número mayor que x, imprima el último elemento
  4. 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: 
 

  1. El algoritmo se puede implementar de forma recursiva o mediante iteración, pero la idea básica sigue siendo la misma.
  2. Hay algunos casos base para manejar. 
    1. Si no hay un número mayor que x, imprima el último elemento
    2. Si el primer número es mayor que x, imprima -1
  3. cree tres variables bajo = 0 , medio y alto = n-1 y otra variable para almacenar la respuesta
  4. Ejecute un bucle o recurse hasta que, a menos que, low sea menor o igual que high.
  5. 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.
  6. De lo contrario, actualice el alto, es decir, alto = medio – 1
  7. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *