fork download
copy 
  1. // Nathanael Schwartz                 CS1A                 Chapter 8, P. 515, #8
  2. //
  3. /*******************************************************************************
  4.  *
  5.  * COUNT SEARCH COMPARISONS
  6.  * _____________________________________________________________________________
  7.  * This program stores at least 20 integers in an array,  and allows the user to
  8.  * search for a value using both linear and binary search algorithms. The 
  9.  * program counts the number of comparisons each search makes.
  10.  * _____________________________________________________________________________
  11.  * INPUT
  12.  *   target          : The value to search for in the array
  13.  *
  14.  * OUTPUT
  15.  *   linearCount     : Number of comparisons made by linear search
  16.  *   binaryCount     : Number of comparisons made by binary search
  17.  *
  18.  ******************************************************************************/
  19.  
  20. #include <iostream>
  21. using namespace std;
  22.  
  23. // Function prototypes
  24. int linearSearch(const int[], int, int, int&);
  25. int binarySearch(const int[], int, int, int&);
  26. void selectionSort(int[], int);
  27.  
  28. int main() {
  29.     const int SIZE = 20;
  30.     int numbers[SIZE] = {35, 17, 48, 10, 26, 55, 13, 49, 18, 72,
  31.                          29, 34, 65, 31, 12, 22, 50, 75, 61, 43};
  32.     int target, linearCount = 0, binaryCount = 0;
  33.  
  34.     // Input: Prompt the user to enter the value to search for
  35.     cout << "Enter the value to search for: \n";
  36.     cin >> target;
  37.  
  38.     // Perform linear search and display comparisons
  39.     int linearResult = linearSearch(numbers, SIZE, target, linearCount);
  40.     if (linearResult != -1) {
  41.         cout << "Linear Search: Value found at index " << linearResult 
  42.              << " with " << linearCount << " comparisons.\n";
  43.     } else {
  44.         cout << "Linear Search: Value not found after " << linearCount;
  45.         cout << " comparisons.\n";
  46.     }
  47.  
  48.     // Sort the array for binary search
  49.     selectionSort(numbers, SIZE);
  50.  
  51.     // Perform binary search and display comparisons
  52.     int binaryResult = binarySearch(numbers, SIZE, target, binaryCount);
  53.     if (binaryResult != -1) {
  54.         cout << "Binary Search: Value found at index " << binaryResult 
  55.              << " with " << binaryCount << " comparisons.\n";
  56.     } else {
  57.         cout << "Binary Search: Value not found after " << binaryCount;
  58.         cout << " comparisons.\n";
  59.     }
  60.  
  61.     return 0;
  62. }
  63.  
  64. /**************************************************************
  65.  *                       linearSearch                         *
  66.  * This function performs a linear search for a target value  *
  67.  * in an array. It returns the index if found, or -1 if not.  *
  68.  * It also counts the number of comparisons made.             *
  69.  **************************************************************/
  70. int linearSearch(const int array[], int size, int target, int &count) {
  71.     for (int i = 0; i < size; i++) {
  72.         count++; // Increment comparison count
  73.         if (array[i] == target) {
  74.             return i; // Target found
  75.         }
  76.     }
  77.     return -1; // Target not found
  78. }
  79.  
  80. /**************************************************************
  81.  *                       binarySearch                         *
  82.  * This function performs a binary search for a target value  *
  83.  * in a sorted array. It returns the index if found, or -1 if *
  84.  * not. It also counts the number of comparisons made.        *
  85.  **************************************************************/
  86. int binarySearch(const int array[], int size, int target, int &count) {
  87.     int low = 0;
  88.     int high = size - 1;
  89.  
  90.     while (low <= high) {
  91.         int mid = (low + high) / 2;
  92.         count++; // Increment comparison count
  93.         if (array[mid] == target) {
  94.             return mid; // Target found
  95.         } else if (array[mid] < target) {
  96.             low = mid + 1; // Search right half
  97.         } else {
  98.             high = mid - 1; // Search left half
  99.         }
  100.     }
  101.     return -1; // Target not found
  102. }
  103.  
  104. /**************************************************************
  105.  *                        selectionSort                       *
  106.  * This function sorts an integer array in ascending order    *
  107.  * using the selection sort algorithm.                        *
  108.  **************************************************************/
  109. void selectionSort(int array[], int size) {
  110.     for (int start = 0; start < size - 1; start++) {
  111.         int minIndex = start;
  112.         for (int index = start + 1; index < size; index++) {
  113.             if (array[index] < array[minIndex]) {
  114.                 minIndex = index;
  115.             }
  116.         }
  117.         // Swap the found minimum element with the first element
  118.         int temp = array[minIndex];
  119.         array[minIndex] = array[start];
  120.         array[start] = temp;
  121.     }
  122. }
  123.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
65
stdout
copy 
Enter the value to search for: 
Linear Search: Value found at index 12 with 13 comparisons.
Binary Search: Value found at index 17 with 3 comparisons.
https://ideone.com/fGHqRG
language:
C++ (gcc 8.3)
created:
344 days 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!