fork download
copy 
  1. // Timothy Price				CS1A				Ch 8 Challenge 8
  2. /******************************************************************************
  3.  * Compare search algorithms 
  4.  * 
  5.  * Compares the efficiency of linear search and binary search algorithms by 
  6.  * locating a target value within a sorted array of integers and displaying 
  7.  * their performance metrics on the screen.
  8.  * Inputs:
  9.  *  A target integer value to locate 
  10.  *  An array of 20 sorted integers 
  11.  * 
  12.  * Outputs:
  13.  *  The index position where the target value is found (or a not-found status)
  14.  *  The total number of comparisons made by the linear search algorithm
  15.  *  The total number of comparisons made by the binary search algorithm
  16.  *****************************************************************************/
  17.  
  18. #include <iostream>
  19.  
  20. using namespace std;
  21.  
  22. // Function prototypes
  23. int linearSearch(const int arr[], int size, int target, int& comparisons);
  24. int binarySearch(const int arr[], int size, int target, int& comparisons);
  25.  
  26. int main() {
  27.     // Array of 20 sorted integers
  28.     const int SIZE = 20;
  29.     int numbers[SIZE] = {
  30.         12, 18, 25, 31, 44, 52, 63, 70, 78, 85,
  31.         92, 105, 112, 120, 135, 142, 155, 168, 180, 195
  32.     };
  33.  
  34.     int target = 12; // The value we want to locate
  35.     int linearComparisons = 0;
  36.     int binaryComparisons = 0;
  37.  
  38.     cout << "Searching for target value: " << target << endl;
  39.     cout << "----------------------------------------" << endl;
  40.  
  41.     // Call Linear Search
  42.     int linearIndex = linearSearch(numbers, SIZE, target, linearComparisons);
  43.     if (linearIndex != -1) {
  44.         cout << "Linear Search:" << endl;
  45.         cout << "  - Status: Found at index " << linearIndex << endl;
  46.         cout << "  - Comparisons made: " << linearComparisons << endl << endl;
  47.     } else {
  48.         cout << "Linear Search: Value not found. Comparisons: ";
  49.         cout << linearComparisons << endl << endl;
  50.     }
  51.  
  52.     // Call Binary Search
  53.     int binaryIndex = binarySearch(numbers, SIZE, target, binaryComparisons);
  54.     if (binaryIndex != -1) {
  55.         cout << "Binary Search:" << endl;
  56.         cout << "  - Status: Found at index " << binaryIndex << endl;
  57.         cout << "  - Comparisons made: " << binaryComparisons << endl << endl;
  58.     } else {
  59.         cout << "Binary Search: Value not found. Comparisons: "; 
  60.         cout << binaryComparisons << endl << endl;
  61.     }
  62.  
  63.     return 0;
  64. }
  65.  
  66. // Function that performs a linear search and counts comparisons
  67. int linearSearch(const int arr[], int size, int target, int& comparisons) {
  68.     comparisons = 0;
  69.     for (int i = 0; i < size; ++i) {
  70.         comparisons++; // Increment comparison counter for each check
  71.         if (arr[i] == target) {
  72.             return i; // Index where the value was found
  73.         }
  74.     }
  75.     return -1; // Value not found
  76. }
  77.  
  78. // Function that performs a binary search and counts comparisons
  79. int binarySearch(const int arr[], int size, int target, int& comparisons) {
  80.     comparisons = 0;
  81.     int left = 0;
  82.     int right = size - 1;
  83.  
  84.     while (left <= right) {
  85.         int mid = left + (right - left) / 2;
  86.  
  87.         comparisons++; // Count the equality check (arr[mid] == target)
  88.         if (arr[mid] == target) {
  89.             return mid; // Index where the value was found
  90.         }
  91.  
  92.         comparisons++; // Count the relational check (arr[mid] < target)
  93.         if (arr[mid] < target) {
  94.             left = mid + 1;
  95.         } else {
  96.             right = mid - 1;
  97.         }
  98.     }
  99.     return -1; // Value not found
  100. }
Success #stdin #stdout 0s 5340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Searching for target value: 12
----------------------------------------
Linear Search:
  - Status: Found at index 0
  - Comparisons made: 1

Binary Search:
  - Status: Found at index 0
  - Comparisons made: 7
https://ideone.com/F3Fd6i
ch8 - search function comparrison
language:
C++ (gcc 8.3)
created:
1 hour 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!