fork download
copy 
  1. //Devin Scheu                                  CS1A                                    Chapter 8, P. 488, #8
  2. //
  3. /**************************************************************
  4. *
  5. * BENCHMARK LINEAR AND BINARY SEARCH COMPARISONS
  6. * ____________________________________________________________
  7. * This program determines the number of comparisons made by
  8. * linear search and binary search to locate a value in an array.
  9. * ____________________________________________________________
  10. * INPUT
  11. * searchValue : The value to search for in the array
  12. *
  13. * OUTPUT
  14. * linearComparisons : The number of comparisons for linear search
  15. * binaryComparisons : The number of comparisons for binary search
  16. *
  17. **************************************************************/
  18.  
  19. #include <iostream>
  20. #include <iomanip>
  21.  
  22. using namespace std;
  23.  
  24. // Function for linear search comparisons
  25. int linearSearch(const int arr[], int size, int value) {
  26.     int comparisons = 0;
  27.     for (int i = 0; i < size; i++) {
  28.         comparisons++;
  29.         if (arr[i] == value) {
  30.             return comparisons;
  31.         }
  32.     }
  33.     return comparisons;
  34. }
  35.  
  36. // Function for binary search comparisons (array must be sorted)
  37. int binarySearch(const int arr[], int size, int value) {
  38.     int comparisons = 0;
  39.     int low = 0;
  40.     int high = size - 1;
  41.     while (low <= high) {
  42.         int mid = (low + high) / 2;
  43.         comparisons++;
  44.         if (arr[mid] == value) {
  45.             return comparisons;
  46.         } else if (arr[mid] < value) {
  47.             low = mid + 1;
  48.         } else {
  49.             high = mid - 1;
  50.         }
  51.     }
  52.     return comparisons;
  53. }
  54.  
  55. // Function for selection sort
  56. void selectionSort(int arr[], int size) {
  57.     for (int i = 0; i < size - 1; i++) {
  58.         int minIndex = i;
  59.         for (int j = i + 1; j < size; j++) {
  60.             if (arr[j] < arr[minIndex]) {
  61.                 minIndex = j;
  62.             }
  63.         }
  64.         if (minIndex != i) {
  65.             int temp = arr[i];
  66.             arr[i] = arr[minIndex];
  67.             arr[minIndex] = temp;
  68.         }
  69.     }
  70. }
  71.  
  72. int main () {
  73.  
  74. 	//Variable Declarations
  75. 	const int ARRAY_SIZE = 20;                        //OUTPUT     - Size of the array
  76. 	int numbers[ARRAY_SIZE] = {5, 7, 2, 8, 9, 1, 0, 4, 3, 6, 10, 12, 14, 16, 18, 11, 13, 15, 17, 19};
  77. 	int searchValue;                                  //INPUT      - The value to search for in the array
  78. 	int linearComparisons;                            //OUTPUT     - The number of comparisons for linear search
  79. 	int binaryComparisons;                            //OUTPUT     - The number of comparisons for binary search
  80.  
  81. 	//Prompt for Input
  82. 	cout << "Enter the value to search for: ";
  83. 	cin >> searchValue;
  84. 	cout << searchValue << endl;
  85.  
  86. 	//Perform Linear Search
  87. 	linearComparisons = linearSearch(numbers, ARRAY_SIZE, searchValue);
  88.  
  89. 	//Sort the Array for Binary Search
  90. 	selectionSort(numbers, ARRAY_SIZE);
  91.  
  92. 	//Perform Binary Search
  93. 	binaryComparisons = binarySearch(numbers, ARRAY_SIZE, searchValue);
  94.  
  95. 	//Separator and Output Section
  96. 	cout << "-------------------------------------------------------" << endl;
  97. 	cout << "OUTPUT:" << endl;
  98.  
  99. 	//Output Result
  100. 	cout << left << setw(25) << "Linear Comparisons:" << right << setw(15) << linearComparisons << endl;
  101. 	cout << left << setw(25) << "Binary Comparisons:" << right << setw(15) << binaryComparisons << endl;
  102.  
  103. } //end of main()
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
14
stdout
copy 
Enter the value to search for: 14
-------------------------------------------------------
OUTPUT:
Linear Comparisons:                   13
Binary Comparisons:                    2
https://ideone.com/avmXFq
language:
C++ (gcc 8.3)
created:
3 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!