Q&A
このままではコードが読めないので、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください
/** * 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 << a[i] << " "; } cout << endl; } ```ここに言語を入力 コード
今学校の課題でC++を習ってます、Linear Search、(Iterative) Binary Search、(Recursive) Binary Search、 Jump Search の計算速度を下の５つの数字で比べ比較するのが課題です。 •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 計算式は、教授が提供してくれたので間違いはありません（おそらく）。 Linear Searchは問題ないのですが、他の三つの計算速度が常に０か１e06 なのです。 どうか助けてください。 ### 発生している問題・エラーメッセージ 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 ### 該当のソースコード ```ここに言語を入力 コード
試したこと
debug をしていったので、コード自体は動きます。
補足情報（FW/ツールのバージョンなど）
ここにより詳細な情報を記載してください。
回答1件
0
ベストアンサー
要素数を1000000まで増やしてwandboxで試してみました (sort部分を工夫)
Finished in linearSearchNumber 0.00417728 seconds Finished in iterativeBinarySearch 3.978e-05 seconds Finished in recursiveBinarySearch 3.978e-05 seconds
つまり、早すぎて今の要素数では0になります。
そもそも、BinarySearchでは、1000000でも20Step程度で見つかります
現在のPCでは、この程度は測定できないほどの時間で求まるはずです
投稿2019/12/05 10:32
総合スコア2856
あなたの回答
tips
プレビュー
