Home>
/**
 * Searching Project
 * See the Assignment 12 document (CSCI112_A12.pdf) for details.
 *
 * Author: N
 * /
#include<iostream>
#include<ctime>
#include<cmath>
#include<chrono>
using namespace std;
// Prototypes
void duplicate (int [],

 int [],

 int);
void printArray (int [],

 int);
int linearSearch (int [],

 int, int);
int iterativeBinarySearch (int [],

 int, int);
int recursiveBinarySearch (int [],

 int, int, int);
int jumpSearch (int [],

 int, int);
void insertionSort (int [],

 int);

/ **
 * Main Function.
 * /
int main () {
    // int LENGTH = 200000;
    // int LENGTH = 150000;
    // int LENGTH = 100000;
    // int LENGTH = 75000;
    int LENGTH = 50000;
    int numbers [LENGTH];// a single array
    srand ((int) time (0));// random numbers in the range of 1 through LENGTH * 2
    for (int i = 0;i<LENGTH;i ++) {
        numbers [i] = rand ()% (LENGTH * 2) + 1;
    }
    int value = numbers [rand ()% LENGTH + 1];// randomly choose a number to search
    cout<<"value:"<<value;
    cout<<endl;
    auto start = chrono :: system_clock :: now ();// Gets the start time
    linearSearch (numbers, LENGTH, value);
    / **
     * Linear Search Algorithm Calculates the total duration
     * /
    chrono :: duration<double>totalTime = chrono :: system_clock :: now ()-start;// Calculates the total duration (now-start)
    cout<<"Clock stopped."<<endl;
    cout<<"Finished in linearSearchNumber"<<totalTime.count ()<<"seconds"<<endl;
    cout<<endl;

    cout<<"Sorting ..."<<endl;
    insertionSort (numbers, LENGTH);
    cout<<"Done."<<endl;
    LENGTH = sizeof (numbers)/4;// Calculates the length of the array
    start = chrono :: system_clock :: now ();
    iterativeBinarySearch (numbers, LENGTH, value);
    / **
     * Iterative Binary Search Calculates the total duration
     * /
    totalTime = chrono :: system_clock :: now ()-start;// Calculates the total duration (now-start)
    cout<<"Clock stopped."<<endl;
    cout<<"Finished in iterativeBinarySearch"<<totalTime.count ()<<"seconds"<<endl;
    start = chrono :: system_clock :: now ();
    recursiveBinarySearch (numbers, 0, LENGTH-1, value);
    / *** Recursive Binary Search Calculates the total duration
     * /
    cout<<"Clock stopped."<<endl;
    cout<<"Finished in recursiveBinarySearch"<<totalTime.count ()<<"seconds"<<endl;
    start = chrono :: system_clock :: now ();
                                                                                         // Calculates the length of the array
    jumpSearch (numbers, LENGTH, value);
    / **
     * Jump Search Calculates the total duration
     * /
    cout<<"Clock stopped."<<endl;
    cout<<"Finished in jumpSearch"<<totalTime.count ()<<"seconds"<<endl;
    return 0;
}
void insertionSort (int a [],

 int length) {
    for (int i = 1;i<length;i ++) {
        int value = a [i];
        int j = i-1;
        while (j>= 0&&a [j]>value) {
            a [j + 1] = a [j];
            j--;
        }
        a [j + 1] = value;
    }
}
/ **
 * Linear Search Algorithm
 * /
int linearSearch (int a [],

 int length, int searchValue) {
    for (int i = 0;i<length;i ++) {
        if (a [i] == searchValue) {
            return i;// The index we found it at
        }
    }
    return -1;
}

/ **
 * Binary Search Algorithm
 * /
int iterativeBinarySearch (int a [],

 int length, int searchValue) {

    int lowBoundary = 0;
    int highBoundary = length-1;
    while (highBoundary>= lowBoundary) {
        int middle = (highBoundary + lowBoundary)/2;// Calculate middle index
        if (searchValue == a [middle]) {
            return middle;// Return the index we found it at
        }
        else if (searchValue>a [middle]) {
            lowBoundary = middle + 1;// Raise the low boundary
        }
        else {
            highBoundary = middle-1;// Lower the high boundary
        }
    }
    return -1;
}
/ **
 * Recursive Binary Search Algorithm
 * /
int recursiveBinarySearch (int array [],

 int first, int last, int value) {
   if (first>last) {
      return -1;// First base Case
   }
   int middle = (first + last)/2;// Calculate the middle position.
   if (array [middle] == value) {
      return middle;// Second base case
   }
   else if (array [middle]<value) {return recursiveBinarySearch (array, middle + 1, last, value);// Recursive case (Search upper partition/upper half)
   }
   else {
      return recursiveBinarySearch (array, first, middle-1, value);// Recursive case (Search lower partition/lower half)
   }
}

/ **
 * Jump Search Algorithm
 * /
int jumpSearch (int a [],

 int length, int searchValue) {
    int previous = 0;
    int jump = (int) sqrt (length);
    while (a [(jump<length? jump: length-1) -1]<searchValue) {
        previous = jump;
        jump + = jump;
        if (jump>= length) {
            break;
        }
    }
    while (a [previous]<searchValue) {
        previous + = 1;
        if (previous == (jump<length? jump: length)) {
            return -1;
        }
    }
    return a [previous] == searchValue? previous: -1;
}
/ **
 * Simply prints the current values ​​in the array.
 * /
void printArray (int a [],

 int length) {
    cout<<"Current values ​​in the array:"<<endl;
    for (int i = 0;i<length;i ++) {
        cout<</pre>
<p>Enter your language here<br />
Code</p>
<pre><code>`` `###
I'm currently learning C ++ for school assignments, Linear Search, (Iterative) Binary Search, (Recursive) Binary Search,
The challenge is to compare and compare the speed of Jump Search calculations with the five numbers below.
• Run 1: Length of the arrays = 50000
Run2: Length of the arrays = 75000
• Run 3: Length of the arrays = 100000
• Run 4: Length of the arrays = 150000
• Run 5: Length of the arrays = 200000
The formula was provided by the professor, so there is no mistake (probably).
There is no problem with Linear Search, but the other three calculation speeds are always 0 or 1e06.
Please help me.
### Error message
1 warning generated.
value: 98262
Clock stopped.
Finished in linearSearchNumber 5e-05 seconds
Sorting ...
Done.
Clock stopped.
Finished in iterativeBinarySearch 0 seconds
Clock stopped.
Finished in recursiveBinarySearch 0 seconds
Clock stopped.
Finished in jumpSearch 0 seconds
### Applicable source code

Enter your language here code `` `

Because I did debug, the code itself works.

Supplemental information (FW/tool version etc.)

Please provide more detailed information here.

c++
Trends