Dada una array ordenada y un valor x, el techo de x es el elemento más pequeño de una array mayor o igual que x, y el piso es el elemento más grande menor o igual que x. Suponga que la array está ordenada en orden no decreciente. Escribe funciones eficientes para encontrar el piso y el techo de x.
Ejemplos:
For example, let the input array be {1, 2, 8, 10, 10, 12, 19}
For x = 0: floor doesn't exist in array, ceil = 1
For x = 1: floor = 1, ceil = 1
For x = 5: floor = 2, ceil = 8
For x = 20: floor = 19, ceil doesn't exist in array
En los métodos a continuación, hemos implementado solo funciones de búsqueda de techo. La búsqueda de piso se puede implementar de la misma manera.
Método 1 (búsqueda lineal)
Algoritmo para buscar techo de x:
- Si x es menor o igual que el primer elemento de la array, devuelve 0 (índice del primer elemento).
- De lo contrario, busque linealmente un índice i tal que x se encuentre entre arr[i] y arr[i+1].
- Si no encontramos un índice i en el paso 2, devuelve -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
/* Function to get index of ceiling of x in arr[low..high] */
int ceilSearch(int arr[], int low, int high, int x)
{
int i;
/* If x is smaller than or equal to first element,
then return the first element */
if(x <= arr[low])
return low;
/* Otherwise, linearly search for ceil value */
for(i = low; i < high; i++)
{
if(arr[i] == x)
return i;
/* if x lies between arr[i] and arr[i+1] including
arr[i+1], then return arr[i+1] */
if(arr[i] < x && arr[i+1] >= x)
return i+1;
}
/* If we reach here then x is greater than the last element
of the array, return -1 in this case */
return -1;
}
/* Driver code*/
int main()
{
int arr[] = {1, 2, 8, 10, 10, 12, 19};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 3;
int index = ceilSearch(arr, 0, n-1, x);
if(index == -1)
cout << "Ceiling of " << x << " doesn't exist in array ";
else
cout << "ceiling of " << x << " is " << arr[index];
return 0;
}
// This is code is contributed by rathbhupendra
C
#include<stdio.h>
/* Function to get index of ceiling of x in arr[low..high] */
int ceilSearch(int arr[], int low, int high, int x)
{
int i;
/* If x is smaller than or equal to first element,
then return the first element */
if(x <= arr[low])
return low;
/* Otherwise, linearly search for ceil value */
for(i = low; i < high; i++)
{
if(arr[i] == x)
return i;
/* if x lies between arr[i] and arr[i+1] including
arr[i+1], then return arr[i+1] */
if(arr[i] < x && arr[i+1] >= x)
return i+1;
}
/* If we reach here then x is greater than the last element
of the array, return -1 in this case */
return -1;
}
/* Driver program to check above functions */
int main()
{
int arr[] = {1, 2, 8, 10, 10, 12, 19};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 3;
int index = ceilSearch(arr, 0, n-1, x);
if(index == -1)
printf("Ceiling of %d doesn't exist in array ", x);
else
printf("ceiling of %d is %d", x, arr[index]);
getchar();
return 0;
}
Java
class Main
{
/* Function to get index of ceiling
of x in arr[low..high] */
static int ceilSearch(int arr[], int low, int high, int x)
{
int i;
/* If x is smaller than or equal to first
element,then return the first element */
if(x <= arr[low])
return low;
/* Otherwise, linearly search for ceil value */
for(i = low; i < high; i++)
{
if(arr[i] == x)
return i;
/* if x lies between arr[i] and arr[i+1]
including arr[i+1], then return arr[i+1] */
if(arr[i] < x && arr[i+1] >= x)
return i+1;
}
/* If we reach here then x is greater than the
last element of the array, return -1 in this case */
return -1;
}
/* Driver program to check above functions */
public static void main (String[] args)
{
int arr[] = {1, 2, 8, 10, 10, 12, 19};
int n = arr.length;
int x = 3;
int index = ceilSearch(arr, 0, n-1, x);
if(index == -1)
System.out.println("Ceiling of "+x+" doesn't exist in array");
else
System.out.println("ceiling of "+x+" is "+arr[index]);
}
}
Python3
# Function to get index of ceiling of x in arr[low..high] */
def ceilSearch(arr, low, high, x):
# If x is smaller than or equal to first element,
# then return the first element */
if x <= arr[low]:
return low
# Otherwise, linearly search for ceil value */
i = low
for i in range(high):
if arr[i] == x:
return i
# if x lies between arr[i] and arr[i+1] including
# arr[i+1], then return arr[i+1] */
if arr[i] < x and arr[i+1] >= x:
return i+1
# If we reach here then x is greater than the last element
# of the array, return -1 in this case */
return -1
# Driver program to check above functions */
arr = [1, 2, 8, 10, 10, 12, 19]
n = len(arr)
x = 3
index = ceilSearch(arr, 0, n-1, x);
if index == -1:
print ("Ceiling of %d doesn't exist in array "% x)
else:
print ("ceiling of %d is %d"%(x, arr[index]))
# This code is contributed by Shreyanshi Arun
C#
// C# program to find ceiling
// in a sorted array
using System;
class GFG {
// Function to get index of ceiling
// of x in arr[low..high]
static int ceilSearch(int[] arr, int low,
int high, int x)
{
int i;
// If x is smaller than or equal
// to first element, then return
// the first element
if (x <= arr[low])
return low;
// Otherwise, linearly search
// for ceil value
for (i = low; i < high; i++) {
if (arr[i] == x)
return i;
/* if x lies between arr[i] and
arr[i+1] including arr[i+1],
then return arr[i+1] */
if (arr[i] < x && arr[i + 1] >= x)
return i + 1;
}
/* If we reach here then x is
greater than the last element
of the array, return -1 in
this case */
return -1;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
int n = arr.Length;
int x = 3;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
Console.Write("Ceiling of " + x +
" doesn't exist in array");
else
Console.Write("ceiling of " + x +
" is " + arr[index]);
}
}
// This code is contributed by Sam007.
PHP
<?php
// Function to get index of
// ceiling of x in arr[low..high]
function ceilSearch($arr, $low, $high, $x)
{
// If x is smaller than or equal
// to first element, then return
// the first element
if($x <= $arr[$low])
return $low;
// Otherwise, linearly search
// for ceil value
for($i = $low; $i < $high; $i++)
{
if($arr[$i] == $x)
return $i;
// if x lies between arr[i] and
// arr[i+1] including arr[i+1],
// then return arr[i+1]
if($arr[$i] < $x &&
$arr[$i + 1] >= $x)
return $i + 1;
}
// If we reach here then x is greater
// than the last element of the array,
// return -1 in this case
return -1;
}
// Driver Code
$arr = array(1, 2, 8, 10, 10, 12, 19);
$n = sizeof($arr);
$x = 3;
$index = ceilSearch($arr, 0, $n - 1, $x);
if($index == -1)
echo("Ceiling of " . $x .
" doesn't exist in array ");
else
echo("ceiling of " . $x . " is " .
$arr[$index]);
// This code is contributed by Ajit.
?>
Javascript
<script>
/* Function to get index of ceiling of
x in arr[low..high] */
function ceilSearch(arr, low, high, x)
{
let i;
/* If x is smaller than or equal to first element,
then return the first element */
if(x <= arr[low])
return low;
/* Otherwise, linearly search for ceil value */
for(i = low; i < high; i++)
{
if(arr[i] == x)
return i;
/* if x lies between arr[i] and arr[i+1] including
arr[i+1], then return arr[i+1] */
if(arr[i] < x && arr[i+1] >= x)
return i+1;
}
/* If we reach here then
x is greater than the last element
of the array, return -1 in this case */
return -1;
}
// driver code
let arr = [1, 2, 8, 10, 10, 12, 19];
let n = arr.length;
let x = 3;
let index = ceilSearch(arr, 0, n-1, x);
if(index == -1)
document.write("Ceiling of " + x + " doesn't exist in array ");
else
document.write ("ceiling of " + x + " is " + arr[index]);
</script>
Producción
ceiling of 3 is 8
Complejidad de Tiempo: O(n), Espacio Auxiliar: O(1)
Método 2 (búsqueda binaria)
En lugar de usar la búsqueda lineal, aquí se usa la búsqueda binaria para encontrar el índice. La búsqueda binaria reduce la complejidad del tiempo a O (Iniciar sesión).
C++
#include <bits/stdc++.h>
using namespace std;
/* Function to get index of
ceiling of x in arr[low..high]*/
int ceilSearch(int arr[], int low, int high, int x)
{
int mid;
/* If x is smaller than
or equal to the first element,
then return the first element */
if (x <= arr[low])
return low;
/* If x is greater than the last element,
then return -1 */
if (x > arr[high])
return -1;
/* get the index of middle element of arr[low..high]*/
mid = (low + high) / 2; /* low + (high - low)/2 */
/* If x is same as middle element,
then return mid */
if (arr[mid] == x)
return mid;
/* If x is greater than arr[mid],
then either arr[mid + 1] is ceiling of x
or ceiling lies in arr[mid+1...high] */
else if (arr[mid] < x) {
if (mid + 1 <= high && x <= arr[mid + 1])
return mid + 1;
else
return ceilSearch(arr, mid + 1, high, x);
}
/* If x is smaller than arr[mid],
then either arr[mid] is ceiling of x
or ceiling lies in arr[low...mid-1] */
else {
if (mid - 1 >= low && x > arr[mid - 1])
return mid;
else
return ceilSearch(arr, low, mid - 1, x);
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 20;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
cout << "Ceiling of " << x
<< " doesn't exist in array ";
else
cout << "ceiling of " << x << " is " << arr[index];
return 0;
}
// This code is contributed by rathbhupendra
C
#include <stdio.h>
/* Function to get index of ceiling of x in arr[low..high]*/
int ceilSearch(int arr[], int low, int high, int x)
{
int mid;
/* If x is smaller than or equal to the first element,
then return the first element */
if (x <= arr[low])
return low;
/* If x is greater than the last element, then return -1
*/
if (x > arr[high])
return -1;
/* get the index of middle element of arr[low..high]*/
mid = (low + high) / 2; /* low + (high - low)/2 */
/* If x is same as middle element, then return mid */
if (arr[mid] == x)
return mid;
/* If x is greater than arr[mid], then either arr[mid +
1] is ceiling of x or ceiling lies in
arr[mid+1...high] */
else if (arr[mid] < x) {
if (mid + 1 <= high && x <= arr[mid + 1])
return mid + 1;
else
return ceilSearch(arr, mid + 1, high, x);
}
/* If x is smaller than arr[mid], then either arr[mid]
is ceiling of x or ceiling lies in arr[low...mid-1]
*/
else {
if (mid - 1 >= low && x > arr[mid - 1])
return mid;
else
return ceilSearch(arr, low, mid - 1, x);
}
}
/* Driver program to check above functions */
int main()
{
int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 20;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
printf("Ceiling of %d doesn't exist in array ", x);
else
printf("ceiling of %d is %d", x, arr[index]);
getchar();
return 0;
}
Java
class Main {
/* Function to get index of
ceiling of x in arr[low..high]*/
static int ceilSearch(int arr[], int low, int high,
int x)
{
// base condition if length of arr == 0 then return
// -1
if (high == 0) {
return -1;
}
/* this while loop function will run until condition
not break once condition break loop will return
start and ans is low which will be next smallest
greater than target which is ceiling*/
while (low <= high) {
int mid
= low + (high - low) / 2; // calculate mid
if (x == arr[mid]) {
return mid;
}
if (x < arr[mid]) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return low;
}
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
if( x < mid) yes set high = mid -1;
step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
if( x < mid) no set low = mid + 1;
step 3 : {1, 2, 8 = high,low,low, 10, 10, 12, 19};
if( x == mid ) yes return mid
if(x < mid ) no low = mid + 1
step 4 : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
check while(low < = high)
condition break and return low which will
next greater of target */
/* Driver program to check above functions */
public static void main(String[] args)
{
int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
int n = arr.length;
int x = 8;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
System.out.println("Ceiling of " + x
+ " doesn't exist in array");
else
System.out.println("ceiling of " + x + " is "
+ arr[index]);
}
}
Python3
# Function to get index of ceiling of x in arr[low..high]*/
def ceilSearch(arr, low, high, x):
# If x is smaller than or equal to the first element,
# then return the first element */
if x <= arr[low]:
return low
# If x is greater than the last element, then return -1 */
if x > arr[high]:
return -1
# get the index of middle element of arr[low..high]*/
mid = (low + high)/2; # low + (high - low)/2 */
# If x is same as middle element, then return mid */
if arr[mid] == x:
return mid
# If x is greater than arr[mid], then either arr[mid + 1]
# is ceiling of x or ceiling lies in arr[mid+1...high] */
elif arr[mid] < x:
if mid + 1 <= high and x <= arr[mid+1]:
return mid + 1
else:
return ceilSearch(arr, mid+1, high, x)
# If x is smaller than arr[mid], then either arr[mid]
# is ceiling of x or ceiling lies in arr[low...mid-1] */
else:
if mid - 1 >= low and x > arr[mid-1]:
return mid
else:
return ceilSearch(arr, low, mid - 1, x)
# Driver program to check above functions
arr = [1, 2, 8, 10, 10, 12, 19]
n = len(arr)
x = 20
index = ceilSearch(arr, 0, n-1, x);
if index == -1:
print ("Ceiling of %d doesn't exist in array "% x)
else:
print ("ceiling of %d is %d"%(x, arr[index]))
# This code is contributed by Shreyanshi Arun
C#
// C# program to find ceiling
// in a sorted array
using System;
class GFG {
// Function to get index of ceiling
// of x in arr[low..high]
static int ceilSearch(int[] arr, int low, int high,
int x)
{
int mid;
// If x is smaller than or equal
// to the first element, then
// return the first element.
if (x <= arr[low])
return low;
// If x is greater than the last
// element, then return -1
if (x > arr[high])
return -1;
// get the index of middle
// element of arr[low..high]
mid = (low + high) / 2;
// low + (high - low)/2
// If x is same as middle
// element then return mid
if (arr[mid] == x)
return mid;
// If x is greater than arr[mid],
// then either arr[mid + 1] is
// ceiling of x or ceiling lies
// in arr[mid+1...high]
else if (arr[mid] < x) {
if (mid + 1 <= high && x <= arr[mid + 1])
return mid + 1;
else
return ceilSearch(arr, mid + 1, high, x);
}
// If x is smaller than arr[mid],
// then either arr[mid] is ceiling
// of x or ceiling lies in
// arr[low...mid-1]
else {
if (mid - 1 >= low && x > arr[mid - 1])
return mid;
else
return ceilSearch(arr, low, mid - 1, x);
}
}
// Driver code
public static void Main()
{
int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
int n = arr.Length;
int x = 8;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
Console.Write("Ceiling of " + x
+ " doesn't exist in array");
else
Console.Write("ceiling of " + x + " is "
+ arr[index]);
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP Program for Ceiling in
// a sorted array
// Function to get index of ceiling
// of x in arr[low..high]
function ceilSearch($arr, $low,
$high, $x)
{
$mid;
/* If x is smaller than or
equal to the first element,
then return the first element */
if($x <= $arr[$low])
return $low;
/* If x is greater than the
last element, then return
-1 */
if($x > $arr[$high])
return -1;
/* get the index of middle
element of arr[low..high] */
// low + (high - low)/2
$mid = ($low + $high)/2;
/* If x is same as middle element,
then return mid */
if($arr[$mid] == $x)
return $mid;
/* If x is greater than arr[mid],
then either arr[mid + 1] is
ceiling of x or ceiling lies
in arr[mid+1...high] */
else if($arr[$mid] < $x)
{
if($mid + 1 <= $high &&
$x <= $arr[$mid + 1])
return $mid + 1;
else
return ceilSearch($arr, $mid + 1,
$high, $x);
}
/* If x is smaller than arr[mid],
then either arr[mid] is ceiling
of x or ceiling lies in
arr[low....mid-1] */
else
{
if($mid - 1 >= $low &&
$x > $arr[$mid - 1])
return $mid;
else
return ceilSearch($arr, $low,
$mid - 1, $x);
}
}
// Driver Code
$arr = array(1, 2, 8, 10, 10, 12, 19);
$n = sizeof($arr);
$x = 20;
$index = ceilSearch($arr, 0, $n - 1, $x);
if($index == -1)
echo("Ceiling of $x doesn't exist in array ");
else
echo("ceiling of $x is");
echo(isset($arr[$index]));
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript Program for Ceiling in
// a sorted array
// Function to get index of ceiling
// of x in arr[low..high]
function ceilSearch(arr, low, high, x)
{
let mid;
/* If x is smaller than or
equal to the first element,
then return the first element */
if(x <= arr[low])
return low;
/* If x is greater than the
last element, then return
-1 */
if(x > arr[high])
return -1;
/* get the index of middle
element of arr[low..high] */
// low + (high - low)/2
mid = (low + high)/2;
/* If x is same as middle element,
then return mid */
if(arr[mid] == x)
return mid;
/* If x is greater than arr[mid],
then either arr[mid + 1] is
ceiling of x or ceiling lies
in arr[mid+1...high] */
else if(arr[mid] < x)
{
if(mid + 1 <= high && x <= arr[mid + 1])
return mid + 1;
else
return ceilSearch(arr, mid + 1, high, x);
}
/* If x is smaller than arr[mid],
then either arr[mid] is ceiling
of x or ceiling lies in
arr[low....mid-1] */
else
{
if(mid - 1 >= low && x > arr[mid - 1])
return mid;
else
return ceilSearch(arr, low, mid - 1, x);
}
}
// Driver Code
let arr = [1, 2, 8, 10, 10, 12, 19];
let n = arr.length;
let x = 20;
let index = ceilSearch(arr, 0, n - 1, x);
if(index == -1){
document.write(`Ceiling of ${x} doesn't exist in array `);
}else{
document.write(`ceiling of ${x} is ${arr[index]}`);
}
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
Ceiling of 20 doesn't exist in array
Complejidad de tiempo: O(log(n)), Espacio auxiliar: O(1)
Otra implementación del método 2:
Al igual que el método anterior, aquí también se usa la búsqueda binaria, pero la lógica del código es diferente en lugar de muchas, si de lo contrario verifico, simplemente regresaré y lo entenderé a través de los pasos a continuación:
Paso 1: {bajo->1, 2, 8, 10<-medio, 10, 12, 19<-alto};
if( x < mid) yes set high = mid -1;
Paso 2: { bajo ->1, 2 <-medio, 8 <-alto, 10, 10, 12, 19};
if( x < mid) no set low = mid + 1;
Paso 3: {1, 2, 8<-alto, bajo, medio, 10, 10, 12, 19};
if( x == mid ) yes return mid if(x < mid ) no low = mid + 1
Paso 4: {1, 2, 8<-alto, medio, 10<-bajo, 10, 12, 19};
check while(low =< high)
condición de ruptura y retorno bajo que es mi techo de destino.
C++
#include <bits/stdc++.h>
using namespace std;
/* Function to get index of
ceiling of x in arr[low..high]*/
int ceilSearch(int arr[], int low, int high, int x)
{
// base condition if length of arr == 0 then return -1
if (x == 0) {
return -1;
}
int mid;
// this while loop function will run until condition not
// break once condition break loop will return start and
// ans is low which will be next smallest greater than
// target which is ceiling
while (low <= high) {
mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
else if (x < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
return low;
}
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
if( x < mid) yes set high = mid -1;
step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12,
19}; if( x < mid) no set low = mid + 1; step 3 : {1, 2, 8
= high,low,low, 10, 10, 12, 19}; if( x == mid ) yes
return mid if(x < mid ) no low = mid + 1 step 4 : {1, 2,
8 = high,mid, 10 = low, 10, 12, 19}; check while(low < =
high) condition break and return low which will next
greater of target */
/* Driver program to check above functions */
int main()
{
int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 8;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
printf("Ceiling of %d does not exist in an array", x);
else
printf("Ceiling of %d is %d", x, arr[index]);
return 0;
}
C
#include <stdio.h>
// Function to get index of ceiling of x in arr[low..high]
int ceilSearch(int arr[], int low, int high, int x)
{
// base condition if length of arr == 0 then return -1
if (x == 0) {
return -1;
}
int mid;
// this while loop function will run until condition not
// break once condition break loop will return start and
// ans is low which will be next smallest greater than
// target which is ceiling
while (low <= high) {
mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
else if (x < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
return low;
}
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
if( x < mid) yes set high = mid -1;
step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12,
19}; if( x < mid) no set low = mid + 1; step 3 : {1, 2, 8
= high,low,low, 10, 10, 12, 19}; if( x == mid ) yes
return mid if(x < mid ) no low = mid + 1 step 4 : {1, 2,
8 = high,mid, 10 = low, 10, 12, 19}; check while(low < =
high) condition break and return low which will next
greater of target */
/* Driver program to check above functions */
int main()
{
int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 8;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
printf("Ceiling of %d does not exist in an array", x);
else
printf("Ceiling of %d is %d", x, arr[index]);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
class Main {
/* Function to get index of
ceiling of x in arr[low..high]*/
static int ceilSearch(int arr[], int low, int high,
int x)
{
// base condition if length of arr == 0 then return
// -1
if (x == 0) {
return -1;
}
/* this while loop function will run until condition
not break once condition break loop will return
start and ans is low which will be next smallest
greater than target which is ceiling*/
while (low <= high) {
int mid
= low + (high - low) / 2; // calculate mid
if (x == arr[mid]) {
return mid;
}
if (x < arr[mid]) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return low;
}
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
if( x < mid) yes set high = mid -1;
step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
if( x < mid) no set low = mid + 1;
step 3 : {1, 2, 8 = high,low,low, 10, 10, 12, 19};
if( x == mid ) yes return mid
if(x < mid ) no low = mid + 1
step 4 : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
check while(low < = high)
condition break and return low which will
next greater of target */
/* Driver program to check above functions */
public static void main(String[] args)
{
int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
int n = arr.length;
int x = 8;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
System.out.println("Ceiling of " + x
+ " doesn't exist in array");
else
System.out.println("ceiling of " + x + " is "
+ arr[index]);
}
}
C#
// C# program for the above approach
using System;
class GFG
{
/* Function to get index of
ceiling of x in arr[low..high]*/
static int ceilSearch(int[] arr, int low, int high, int x)
{
// base condition if length of arr == 0 then return -1
if (x == 0)
{
return -1;
}
/* this while loop function will run until condition not break once condition break
loop will return start and ans is low which will be next smallest greater than target
which is ceiling*/
while (low <= high)
{
int mid = low + (high - low) / 2;//calculate mid
if (x == arr[mid])
{
return mid;
}
if (x < arr[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return low;
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
if( x < mid) yes set high = mid -1;
step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
if( x < mid) no set low = mid + 1;
step 3 : {1, 2, 8 = high,low,low, 10, 10, 12, 19};
if( x == mid ) yes return mid
if(x < mid ) no low = mid + 1
step 4 : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
check while(low < = high)
condition break and return low which will next greater of target */
}
/* Driver program to check above functions */
public static void Main()
{
int[] arr = { 1, 2, 8, 10, 10, 12, 19 };
int n = arr.Length;
int x = 8;
int index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
Console.WriteLine("Ceiling of " + x + " doesn't exist in array");
else
Console.WriteLine("ceiling of " + x + " is " + arr[index]);
}
}
Javascript
//JS program to implement the approach
/* Function to get index of
ceiling of x in arr[low..high]*/
function ceilSearch(arr, low, high, x)
{
// base condition if length of arr == 0 then return -1
if (x == 0)
{
return -1;
}
var mid;
/* this while loop function will run until
condition not break once condition break
loop will return start and ans is low
which will be next smallest greater than target
which is ceiling*/
while (low <= high)
{
mid = low + (high - low) / 2;
if (arr[mid] == x)
{
return mid;
}
else if (x < arr[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return low;
}
/* step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
if( x < mid) yes set high = mid -1;
step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
if( x < mid) no set low = mid + 1;
step 3 : {1, 2, 8 = high,low,low, 10, 10, 12, 19};
if( x == mid ) yes return mid
if(x < mid ) no low = mid + 1
step 4 : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
check while(low < = high)
condition break and return low which will next greater of target */
/* Driver program to check above functions */
var arr = [1, 2, 8, 10, 10, 12, 19];
var n = arr.length;
var x = 8;
var index = ceilSearch(arr, 0, n - 1, x);
if (index == -1)
{
console.log("Ceiling of " + x + " does not exist in an array");
}
else
{
console.log("Ceiling of " + x + " is " + arr[index]);
}
Python3
# Function to get index of ceiling of x in arr[low..high]
def ceilSearch(arr, low, high, x):
# base condition if length of arr == 0 then return -1
if (x == 0):
return -1
"""this while loop function will run until
condition not break once condition break
loop will return start and ans is low
which will be next smallest greater than target
which is ceiling"""
while (low <= high):
mid = low + (high - low) / 2
mid = int(mid)
if (arr[mid] == x):
return mid
elif (x < arr[mid]):
high = mid - 1
else:
low = mid + 1
return low
""" step 1 : { low = 1, 2, 8, 10= mid, 10, 12, 19= high};
if( x < mid) yes set high = mid -1;
step 2 : { low = 1, 2 = mid, 8 = high, 10, 10, 12, 19};
if( x < mid) no set low = mid + 1;
step 3 : {1, 2, 8 = high,low,low, 10, 10, 12, 19};
if( x == mid ) yes return mid
if(x < mid ) no low = mid + 1
step 4 : {1, 2, 8 = high,mid, 10 = low, 10, 12, 19};
check while(low < = high)
condition break and return low which will next greater of target """
# Driver program to check above functions
arr = [1, 2, 8, 10, 10, 12, 19]
n = len(arr)
x = 8
index = ceilSearch(arr, 0, n - 1, x)
if (index == -1):
print("Ceiling of", x, "does not exist in an array")
else:
print("Ceiling of", x, "is", arr[index])
Producción
Ceiling of 8 is 8
Complejidad de tiempo: O(log(n)), donde n es la longitud de la array dada, Espacio auxiliar: O(1)
Artículos relacionados:
Piso en una array ordenada
Encuentra piso y techo en una array no ordenada
Escriba comentarios si encuentra que alguno de los códigos/algoritmos anteriores es incorrecto, encuentra mejores formas de resolver el mismo problema o desea compartir el código para la implementación del piso.
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