fork(2) download 
  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 = 0;
  46. 	int r = 100;
  47.  
  48. 	int t = find_t(l, r);
  49.  
  50. 	cout << "The answer is " << t << endl;
  51.  
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 5476KB
comments (?)
stdin 
Standard input is empty
stdout 
Iteration #1 in range [0, 100) the midpoint 50 is false
Iteration #2 in range [0, 50) the midpoint 25 is true
Iteration #3 in range [25, 50) the midpoint 37 is true
Iteration #4 in range [37, 50) the midpoint 43 is false
Iteration #5 in range [37, 43) the midpoint 40 is true
Iteration #6 in range [40, 43) the midpoint 41 is true
Iteration #7 in range [41, 43) the midpoint 42 is true
The answer is 42
https://ideone.com/9LBSYI
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!