fork download
copy 
  1. //Sam Partovi                      CS1A                     Chapter 8, P 488, #8
  2. //
  3. /*******************************************************************************
  4. * COMPARE SEARCH ALGORITHM EFFICIENCY
  5. * ____________________________________________________________
  6. * This program compares the efficiencies of linear and binary search algorithms
  7. * by searching through an array of specified values and counting the number of 
  8. * comparisons needed for each algorithm to complete the search.
  9. * ____________________________________________________________
  10. *INPUT
  11. * ARRAY_SIZE: Size of array to be searched
  12. * targetValue: Given number to be located in array
  13. * array: Array of numbers to be searched
  14. *OUTPUT
  15. * linearCounter: Counter for linear search comparisons
  16. * binaryCounter: Counter for binary search comparisons
  17. * linearResult:  Index of number found via linear search
  18. * binaryResult:  Index of number found via binary search
  19. ******************************************************************************/
  20. #include <iostream>
  21. #include <iomanip>
  22. using namespace std;
  23.  
  24. const int ARRAY_SIZE = 20;   //INPUT - Size of array to be searched
  25.  
  26. int LinearSearch(const int, int, int[], int&);
  27. int BinarySearch(const int, int, int[], int&);
  28.  
  29. int main() {
  30.  int targetValue = 3000;    //INPUT - Given number to be located in array
  31.  
  32. //INPUT - Array of numbers to be searched
  33.  int array[ARRAY_SIZE] = {124, 125, 163, 168, 182, 185, 195, 204, 206, 209, 785,
  34.                           858, 915, 1592, 1597, 2000, 2005, 2025, 2090, 3000};
  35.  
  36.  int linearCounter = 0;     //OUTPUT - Counter for linear search comparisons
  37.  int binaryCounter = 0;     //OUTPUT - Counter for binary search comparisons
  38.  int linearResult;          //OUTPUT - Index of number found via linear search
  39.  int binaryResult;          //OUTPUT - Index of number found via binary search
  40.  
  41. //Call LinearSearch function
  42.  linearResult = LinearSearch(ARRAY_SIZE, targetValue, array, linearCounter);
  43.  
  44. //Display linear search results
  45.  cout << "LINEAR SEARCH: Number is in index " << linearResult;
  46.  cout << "\nTook " << linearCounter << " comparisons";
  47.  
  48. //Format output
  49.  cout << "\n-----------------------------------\n";
  50.  
  51. //Call BinarySearch function
  52.  binaryResult = BinarySearch(ARRAY_SIZE, targetValue, array, binaryCounter);
  53.  
  54. //Display binary search results
  55.   cout << "BINARY SEARCH: Number is in index " << binaryResult;
  56.   cout << "\nTook " << binaryCounter << " comparisons\n";
  57.  
  58.  //Determine the most efficient search algorithm
  59.   if(linearCounter < binaryCounter) {
  60.   	cout << "\nThe linear search is more efficient in this case.";
  61.   }
  62.   else if(linearCounter == binaryCounter) {
  63.   	cout << "\nLinear and binary searches are equally efficient in this case.";
  64.   }
  65.   else cout << "\nThe binary search is more efficient in this case.";
  66.  
  67. return 0;
  68. }
  69.  
  70. //******************************************************************************
  71. //Definition for LinearSearch function:
  72. // This function performs a linear search on the given array and returns the
  73. // index of the targetValue and counts the number of comparisons made.
  74. //******************************************************************************
  75. int LinearSearch(const int ARRAY_SIZE, int targetValue, int array[], 
  76.                  int &linearCounter) {
  77.  
  78. //Search for targetValue in array
  79.  for(int i = 0; i < ARRAY_SIZE; i++) {
  80. 	linearCounter++;       //Increment counter
  81. 	if(array[i] == targetValue) {
  82.      return i;
  83.     }
  84.  
  85.  }
  86. 	return -1;
  87. }
  88.  
  89. //******************************************************************************
  90. //Definition for BinarySearch function:
  91. // This function performs a binary search on the given array and returns the
  92. // index of the targetValue and counts the number of comparisons made.
  93. //******************************************************************************
  94. int BinarySearch(const int ARRAY_SIZE, int targetValue, int array[], 
  95.                  int &binaryCounter) {
  96. 	int first = 0;                 //First number in the array
  97. 	int last = ARRAY_SIZE - 1;     //Last number in the array
  98.  
  99. 	while(first <= last) {
  100. 		int middle = (first + last) / 2;       //Find midpoint
  101. 		binaryCounter++;                       //Increment counter
  102. 		if(array[middle] == targetValue) return middle;  //Return if found
  103. 		else if(array[middle] < targetValue) first = middle + 1; //If top half
  104. 		else last = middle - 1;                                 //If bottom half
  105. 	}
  106.  return -1;
  107. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
LINEAR SEARCH: Number is in index 19
Took 20 comparisons
-----------------------------------
BINARY SEARCH: Number is in index 19
Took 5 comparisons

The binary search is more efficient in this case.
https://ideone.com/BgDNhP
CHAPTER 8 (EFFICIENCY)
language:
C++ (gcc 8.3)
created:
5 days 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!