fork download
  1. // Marvyn Jesse De La Torre CS1A Chapter 8 #8 pg.488
  2. //
  3. /*************************************************************
  4. * Search Benchmarks
  5. *
  6. * This program compares linear search and binary search
  7. * by counting the number of comparisons required.
  8. *
  9. * Input:
  10. * num: The number to search for
  11. *
  12. * Output:
  13. * Displays the comparison count for each search method.
  14. *************************************************************/
  15.  
  16. #include <iostream>
  17. using namespace std;
  18.  
  19. int linearSearch(int arr[], int size, int num, int &count);
  20. int binarySearch(int arr[], int size, int num, int &count);
  21.  
  22. int main()
  23. {
  24. int arr[] = {
  25. 3, 6, 9, 12, 15, 18, 21, 24, 27, 30,
  26. 33, 36, 39, 42, 45, 48, 51, 54, 57, 60
  27. };
  28.  
  29. int size = sizeof(arr) / sizeof(arr[0]);
  30. int num;
  31. int linearCount = 0;
  32. int binaryCount = 0;
  33.  
  34. cout << "Enter the number to search for: ";
  35. cin >> num;
  36.  
  37. int linearResult = linearSearch(arr, size, num, linearCount);
  38. int binaryResult = binarySearch(arr, size, num, binaryCount);
  39.  
  40. if (linearResult == -1)
  41. {
  42. cout << "Number was not found using linear search." << endl;
  43. }
  44. else
  45. {
  46. cout << "Linear search found the number." << endl;
  47. }
  48.  
  49. cout << "Linear search comparisons: " << linearCount << endl;
  50.  
  51. if (binaryResult == -1)
  52. {
  53. cout << "Number was not found using binary search." << endl;
  54. }
  55. else
  56. {
  57. cout << "Binary search found the number." << endl;
  58. }
  59.  
  60. cout << "Binary search comparisons: " << binaryCount << endl;
  61.  
  62. return 0;
  63. }
  64.  
  65. int linearSearch(int arr[], int size, int num, int &count)
  66. {
  67. int position = -1;
  68.  
  69. for (int index = 0; index < size && position == -1; index++)
  70. {
  71. count++;
  72.  
  73. if (arr[index] == num)
  74. {
  75. position = index;
  76. }
  77. }
  78.  
  79. return position;
  80. }
  81.  
  82. int binarySearch(int arr[], int size, int num, int &count)
  83. {
  84. int first = 0;
  85. int last = size - 1;
  86. int position = -1;
  87.  
  88. while (position == -1 && first <= last)
  89. {
  90. int middle = (first + last) / 2;
  91.  
  92. count++;
  93.  
  94. if (arr[middle] == num)
  95. {
  96. position = middle;
  97. }
  98. else if (arr[middle] > num)
  99. {
  100. last = middle - 1;
  101. }
  102. else
  103. {
  104. first = middle + 1;
  105. }
  106. }
  107.  
  108. return position;
  109. }
Success #stdin #stdout 0.01s 5332KB
stdin
51 
stdout
Enter the number to search for: Linear search found the number.
Linear search comparisons: 17
Binary search found the number.
Binary search comparisons: 5