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.
-
Answer # 1
Related articles
- i am a beginner i had a bug when i wrote a binary search in c ++
- c ++ - binary search is off by one
- read contents of c ++ text file into binary search tree
- c ++ - unable to compile binary search tree implementation
- code for linear search in c ++
- Example of binary search algorithm implemented by PHP
- Detailed examples of the binary search method of java algorithm
- Java binary search tree implementation code
- C ++ binary search algorithm example
- Detailed Python binary search
- c ++ - atcoder abc 002 d:i want to understand factions by bit full search
- Example implementation method of PHP binary search algorithm
- Python implements binary search algorithm
- C classic algorithm of binary search
- Python binary search and quick sort example
- Java data structure binary search example of binarysearch
- C language binary sort (search) tree example
- Detailed JS binary search algorithm
- Javascript algorithm binary search tree example code
- java algorithm binary search and half search
Trends
I increased the number of elements to 1000000 and tried it with wandbox (devised the sort part)
In other words, it is too early and the number of elements is 0.
In the first place, with BinarySearch, even 1000000 can be found in about 20 Steps
With current PCs, this level should be determined in a time that cannot be measured