fork(137) download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. #include <stdio.h> // C style input and output
  5.  
  6. #define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
  7.  
  8. // largest value <= key
  9. // Invariant: A[l] <= key and A[r] > key
  10. // Boundary: |r - l| = 1
  11. // Input: A[l .... r-1]
  12. // Precondition: A[l] <= key <= A[r]
  13. int Floor(int A[], int l, int r, int key) {
  14. int m;
  15.  
  16. while( r - l > 1 ) {
  17. m = l + (r - l)/2;
  18.  
  19. if( A[m] <= key )
  20. l = m;
  21. else
  22. r = m;
  23. }
  24.  
  25. return A[l];
  26. }
  27.  
  28. int Floor(int A[], int size, int key) {
  29. // Error checking
  30. if( key < A[0] )
  31. return -1; // There is no floor value
  32.  
  33. return Floor(A, 0, size, key);
  34. }
  35.  
  36. void TestCase_01() {
  37. int A[] = { 1, 3, 4, 7, 9, 13, 18, 23 };
  38. int size = ARRAY_SIZE(A);
  39.  
  40. int key;
  41.  
  42. scanf("%d", &key);
  43.  
  44. while( key != -1 ) {
  45. printf("%d\n", Floor(A, size, key));
  46. scanf("%d", &key);
  47. }
  48. }
  49.  
  50. int main() {
  51. TestCase_01();
  52.  
  53. return 0;
  54. }
  55.  
Success #stdin #stdout 0s 2900KB
stdin
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
-1
stdout
-1
1
1
3
4
4
4
7
7
9
9
9
9
13
13
13
13
13
18
18
18
18
18
23
23
23