fork download
copy 
  1. #include <iostream>
  2. #include <cassert>
  3. using namespace std;
  4.  
  5. bool check(int idx) {
  6. 	return idx <= 42;
  7. }
  8.  
  9. int find_t(int l, int r) {
  10. 	assert(check(l) == true);
  11. 	//assert(check(r) == false); // this precondition is not mandatory
  12.  
  13. 	int max_idx_true = l; // highest known integer which satisfies check(idx) == true
  14. 	int min_idx_false = r; // lowest known integer which satisfies check(idx) == false
  15. 	int n = 0; // Number of iterations, not needed but helps analyzing the complexity
  16.  
  17. 	while (max_idx_true+1 < min_idx_false) {
  18. 		++n;
  19.  
  20. 		int mid_idx = (max_idx_true+min_idx_false)/2;
  21.  
  22.     	// Analyze the algorithm in detail
  23.     	// Usually this would be displayed on the standard error (cerr)
  24.     	// but because ideone.com hides the standard error when everything is good
  25.     	// the details are displayed on the standard output instead
  26. 		cout << "Iteration #" << n;
  27. 		cout << " in range [" << max_idx_true << ", " << min_idx_false << ")";
  28. 		cout << " the midpoint " << mid_idx << " is " << boolalpha << check(mid_idx) << noboolalpha;
  29. 		cout << endl;
  30.  
  31. 		if (check(mid_idx)) max_idx_true = mid_idx;
  32. 		else min_idx_false = mid_idx;
  33. 	}
  34.  
  35. 	int t = max_idx_true;
  36.  
  37. 	assert(check(t) == true);
  38. 	assert(t+1 == r || check(t+1) == false);
  39.  
  40. 	return t;
  41. }
  42.  
  43. int main() {
  44. 	// Initial constants
  45. 	int l = -2000000000;
  46. 	int r = 2000000000;
  47.  
  48. 	int t = find_t(l, r);
  49.  
  50. 	cout << "The answer is " << t << endl;
  51.  
  52. 	return 0;
  53. }
Success #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Iteration #1 in range [-2000000000, 2000000000) the midpoint 0 is true
Iteration #2 in range [0, 2000000000) the midpoint 1000000000 is false
Iteration #3 in range [0, 1000000000) the midpoint 500000000 is false
Iteration #4 in range [0, 500000000) the midpoint 250000000 is false
Iteration #5 in range [0, 250000000) the midpoint 125000000 is false
Iteration #6 in range [0, 125000000) the midpoint 62500000 is false
Iteration #7 in range [0, 62500000) the midpoint 31250000 is false
Iteration #8 in range [0, 31250000) the midpoint 15625000 is false
Iteration #9 in range [0, 15625000) the midpoint 7812500 is false
Iteration #10 in range [0, 7812500) the midpoint 3906250 is false
Iteration #11 in range [0, 3906250) the midpoint 1953125 is false
Iteration #12 in range [0, 1953125) the midpoint 976562 is false
Iteration #13 in range [0, 976562) the midpoint 488281 is false
Iteration #14 in range [0, 488281) the midpoint 244140 is false
Iteration #15 in range [0, 244140) the midpoint 122070 is false
Iteration #16 in range [0, 122070) the midpoint 61035 is false
Iteration #17 in range [0, 61035) the midpoint 30517 is false
Iteration #18 in range [0, 30517) the midpoint 15258 is false
Iteration #19 in range [0, 15258) the midpoint 7629 is false
Iteration #20 in range [0, 7629) the midpoint 3814 is false
Iteration #21 in range [0, 3814) the midpoint 1907 is false
Iteration #22 in range [0, 1907) the midpoint 953 is false
Iteration #23 in range [0, 953) the midpoint 476 is false
Iteration #24 in range [0, 476) the midpoint 238 is false
Iteration #25 in range [0, 238) the midpoint 119 is false
Iteration #26 in range [0, 119) the midpoint 59 is false
Iteration #27 in range [0, 59) the midpoint 29 is true
Iteration #28 in range [29, 59) the midpoint 44 is false
Iteration #29 in range [29, 44) the midpoint 36 is true
Iteration #30 in range [36, 44) the midpoint 40 is true
Iteration #31 in range [40, 44) the midpoint 42 is true
Iteration #32 in range [42, 44) the midpoint 43 is false
The answer is 42
https://ideone.com/Fe3YDF
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!