fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // global variable to count total number of comparisons
  5. int comparisons = 0;
  6.  
  7. // Divide & Conquer solution to find minimum and maximum number in an array
  8. void findMinAndMax(int arr[], int low, int high, int& min, int& max)
  9. {
  10. 	// if array contains only one element
  11. 	comparisons += 1;
  12. 	if (low == high)			// common comparison
  13. 	{
  14. 		if (max < arr[low])		// comparison 1
  15. 			max = arr[low];
  16.  
  17. 		if (min > arr[high])	// comparison 2
  18. 			min = arr[high];
  19.  
  20. 		comparisons += 2;
  21. 		return;
  22. 	}
  23.  
  24. 	// if array contains only two elements
  25. 	comparisons += 1;
  26. 	if (high - low == 1)			// common comparison 
  27. 	{
  28. 		if (arr[low] < arr[high])	// comparison 1
  29. 		{
  30. 			if (min > arr[low])		// comparison 2
  31. 				min = arr[low];
  32.  
  33. 			if (max < arr[high])	// comparison 3
  34. 				max = arr[high];
  35. 		}
  36. 		else
  37. 		{
  38. 			if (min > arr[high])	// comparison 2
  39. 				min = arr[high];
  40.  
  41. 			if (max < arr[low])		// comparison 3
  42. 				max = arr[low];
  43. 		}
  44. 		comparisons += 3;
  45. 		return;
  46. 	}
  47.  
  48. 	// find mid element
  49. 	int mid = (low + high) / 2;
  50.  
  51. 	// recuse for left subarray
  52. 	findMinAndMax(arr, low, mid, min, max);
  53.  
  54. 	// recuse for right subarray
  55. 	findMinAndMax(arr, mid + 1, high, min, max);
  56. }
  57.  
  58. int main()
  59. {
  60. 	// int arr[] = { 7, 2, 9, 3, 1, 6, 7, 8, 4};
  61. 	int arr[] = { 7, 2, 9, 3, 1, 6, 7, 8, 4, 5};
  62.  
  63. 	int n = sizeof(arr) / sizeof(arr[0]);
  64.  
  65. 	// initialize minimum element by infinity
  66. 	// initialize maximum element by minus infinity	
  67. 	int max = INT_MIN, min = INT_MAX;
  68.  
  69. 	findMinAndMax(arr, 0, n - 1, min, max);
  70.  
  71. 	cout << "The minimum element in the array is " << min << endl;
  72. 	cout << "The maximum element in the array is " << max << endl;
  73.  
  74. 	cout << "\nTotal number of comparisons is " << comparisons;
  75. 	return 0;
  76. }
  77.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The minimum element in the array is 1
The maximum element in the array is 9

Total number of comparisons is 36
https://ideone.com/mMOMi8
Count total number of comparisons
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!