给定一个排序数组和一个值x，x的上限是数组中大于或等于x的最小元素，下限是小于或等于x的最大元素。假设数组按非降序排序。编写有效的函数来查找x的下限和上限。 例如：
null
For example, let the input array be {1, 2, 8, 10, 10, 12, 19}For x = 0: floor doesn't exist in array, ceil = 1For x = 1: floor = 1, ceil = 1For x = 5: floor = 2, ceil = 8For x = 20: floor = 19, ceil doesn't exist in array
在下面的方法中，我们只实现了上限搜索功能。楼层搜索也可以用同样的方式实现。 方法1（线性搜索） 搜索x的上限的算法： 1） 如果x小于或等于数组中的第一个元素，则返回0（第一个元素的索引） 2） 否则，线性搜索索引i，使x位于arr[i]和arr[i+1]之间。 3） 如果我们在步骤2中没有找到索引i，那么返回-1
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]); } } |
蟒蛇3
# 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> |
输出：
ceiling of 3 is 8
时间复杂性： O（n） 方法2（二进制搜索） 这里使用二进制搜索来查找索引，而不是使用线性搜索。二进制搜索将时间复杂度降低到O（Logn）。
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 (n == 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 samllest greater than target which is ceiling*/ while (low <= high){ int mid = low + (high - low)/ 2 ; //claculate 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) condion 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]); } } |
蟒蛇3
# 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> |
输出：
Ceiling of 20 doesn't exist in array
时间复杂度：O（Logn）
方法2的另一个实现：
与前面的方法一样，这里也使用了二进制搜索，但代码逻辑不同，而不是大量的if-else检查，我将简单地返回，并通过以下步骤让大家理解：
第一步：{low->1,2,8,10
如果（x
第二步：{low->1,2
如果（x
第三步：{1,2,8
如果（x==mid）是，返回mid
如果（x
第四步：{1,2,8
检查时（低=
条件突破和低回报，这是我的目标上限。
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 (n == 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 samllest greater than target which is ceiling*/ while (low <= high){ int mid = low + (high - low)/ 2 ; //claculate 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) condion 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]); } } |
相关文章： 按顺序排列的地板 在未排序的数组中查找地板和天花板 如果您发现上述任何代码/算法不正确，或者找到更好的方法来解决相同的问题，或者希望共享用于现场实现的代码，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
