fork download
copy 
  1. //Andrew Alspaugh                CS1A                     Chapter 8. P. 488. #8.
  2.  
  3. /****************************************************************************
  4. Compare Effieciency of Search Methods
  5. _____________________________________________________________________________
  6. This Program Searches for an integer in two parallel in two different methods
  7. linear and binary searches
  8.  
  9. The program then determines how many comparisons each search method had
  10. _____________________________________________________________________________
  11. //DATA DICTIONARY
  12. 	//Set up Arrays
  13. 	const int SIZE = 20;
  14. 	int Array1[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  15. 	int Array2[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  16.  
  17. 	//User Input
  18. 	int searchFor;
  19.  
  20. 	//Linear Search
  21. 	int i = 0;
  22. 	bool found1 = false;
  23. 	int searches1 = 0;
  24.  
  25. 	//Bubble Sort
  26. 	bool swap;
  27. 	int temp;
  28.  
  29. 	//Binary Search
  30. 	int first = 0;
  31. 	int last = SIZE - 1;
  32. 	int middle;
  33. 	int searches2 = 0;
  34. 	bool found2 = false;
  35. *****************************************************************************/
  36. #include <iostream>
  37. using namespace std;
  38.  
  39. int main() 
  40. {
  41. //DATA DICTIONARY
  42. 	//Set up Arrays
  43. 	const int SIZE = 20;
  44. 	int Array1[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  45. 	int Array2[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  46.  
  47. 	//User Input
  48. 	int searchFor;
  49.  
  50. 	//Linear Search
  51. 	int i = 0;
  52. 	bool found1 = false;
  53. 	int searches1 = 0;
  54.  
  55. 	//Bubble Sort
  56. 	bool swap;
  57. 	int temp;
  58.  
  59. 	//Binary Search
  60. 	int first = 0;
  61. 	int last = SIZE - 1;
  62. 	int middle;
  63. 	int searches2 = 0;
  64. 	bool found2 = false;
  65.  
  66. //INPUT
  67. 	cout << "Enter Integer To Search Arrays For:" << endl;
  68. 	cin >> searchFor;
  69.  
  70.  
  71. //PROCESS
  72. 	//Linear Search // Array1
  73. 	while(i < SIZE && !found1)
  74. 	{
  75. 		searches1++;
  76.  
  77. 		if (Array1[i] == searchFor)
  78. 			found1 = true;
  79.  
  80. 		i++;
  81. 	}
  82.  
  83. 	//Bubble Sort // Array2
  84. 	do
  85. 	{
  86. 		swap = false;
  87. 		for (int count = 0; count < (SIZE - 1); count++)
  88. 		{
  89. 			if(Array2[count] > Array2[count + 1])
  90. 			{
  91. 				temp = Array2[count];
  92. 				Array2[count] = Array2[count + 1];
  93. 				Array2[count + 1] = temp;
  94. 				swap = true;
  95. 			}
  96. 		}
  97. 	} while(swap);
  98.  
  99. 	//Binary Search // Array2
  100. 	while(!found2 && first <= last)
  101. 	{
  102. 		searches2++;
  103.  
  104. 		middle = (first + last) / 2;
  105.  
  106. 		if (Array2[middle] == searchFor)
  107. 			found2 = true;
  108. 		else if (Array2[middle] > searchFor)
  109. 			last = middle - 1;
  110. 		else
  111. 			first = middle + 1;
  112. 	}
  113.  
  114. //OUTPUT
  115.  
  116. 	//Linear Searches Comparisons:
  117. 	if (found1)
  118. 		cout << "Linear Search Had " << searches1 << " Comparisons." << endl;
  119. 	else
  120. 		cout << "Interger Not Found in Array" << endl;
  121.  
  122. 	//Binary Searches Comparisons;
  123. 	if (found2)
  124. 		cout << "Binary Search Had " << searches2 << " Comparisons." << endl;
  125.  
  126. 	return 0;
  127. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
14
stdout
copy 
Enter Integer To Search Arrays For:
Linear Search Had 14 Comparisons.
Binary Search Had 5 Comparisons.
https://ideone.com/h5R0lg
language:
C++ (gcc 8.3)
created:
5 hours 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!