给定一个排序数组和一个值x，x的下限是数组中小于或等于x的最大元素。编写有效函数来查找x的下限。 例如：
null
Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 5Output : 22 is the largest element in arr[] smaller than 5.Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 20Output : 1919 is the largest element inarr[] smaller than 20.Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 0Output : -1Since floor doesn't exist,output is -1.
简单方法 方法： 想法很简单，遍历数组，找到第一个大于x的元素。在找到的元素之前的元素是x的底部。 算法：
- 从头到尾遍历阵列。
- 如果当前元素大于x，打印上一个数字并中断循环。
- 如果没有大于x的数字，则打印最后一个元素
- 如果第一个数字大于x，则打印-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> |
输出：
Floor of 7 is 6.
复杂性分析：
- 时间复杂性： O（n）。 遍历一个数组只需要一个循环，因此时间复杂度为O（n）。
- 空间复杂性： O（1）。 不需要额外的空间，因此空间复杂度是恒定的
有效方法 方法： 问题中有一个陷阱，给定的数组被排序。这个想法是使用 二进制搜索 找到一个数字的底部 十、 在排序数组中，将其与中间元素进行比较，并将搜索空间分成一半。 算法：
- 该算法可以递归实现，也可以通过迭代实现，但基本思想保持不变。
- 有一些基本情况需要处理。
- 如果没有大于x的数字，则打印最后一个元素
- 如果第一个数字大于x，则打印-1
- 创建三个变量 低=0 、中期和中期 高=n-1 和另一个变量来存储答案
- 运行循环或递归，直到且除非low小于或等于high。
- 检查中间( （低+高）/2 )元素小于x，如果是，则更新下限，即 低=中+1 ，并使用中间元素更新答案。在这一步中，我们将搜索空间减少到一半。
- 否则，请更新high，即 高=中–1
- 打印答案。
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> |
输出：
Floor of 7 is 6.
复杂性分析：
- 时间复杂性： O（logn）。 要运行二进制搜索，所需的时间复杂度为O（logn）。
- 空间复杂性： O（1）。 由于不需要额外的空间，因此空间复杂度是恒定的。
本文由 马扬克·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
