1: //profiler_search.cpp
2: //A program to perform timing and operation counts for linear
3: //and binary searches. Also uses the STL sort algorithm to
4: //sort values before binary searches are performed.
6: #include <iostream>
7: #include <iomanip>
8: #include <string>
9: #include <vector>
10: #include <algorithm> //For access to the STL "sort" algorithm
11: #include "utilities.h"
13: using namespace std;
14: using namespace Scobey;
16: //Global variables
17: //These global variables are permissible for the following reasons:
18: //There is only one of each used throughout the program and each is used
19: //in the same way each time it is used, much like the "global object" cout
20: //is used everywhere throughout a program to display output on the screen.
21: RandomGenerator rangen;
22: Stopwatch timer;
23: OperationCounter counter;
24: bool timer_ON = false;
25: bool counter_ON = false;
28: //Function prototypes
29: void Search(/* in */ vector<int>& a);
31: void SearchLinear(/* in */ const vector<int>& a,
32: /* in */ int targetValue,
33: /* in */ int firstPosition,
34: /* in */ int lastPosition,
35: /* out */ int& targetPosition,
36: /* out */ bool& targetFound);
38: void SearchBinary(/* in */ const vector<int>& a,
39: /* in */ int targetValue,
40: /* in */ int firstPosition,
41: /* in */ int lastPosition,
42: /* out */ int& targetPosition,
43: /* out */ bool& targetFound);
45: void DisplayValues(/* in */ const vector<int>& v);
47: void DisplayStatistics();
50: int main()
51: {
52: cout << "\nThis program is a \"search profiler\". It searches "
53: "randomly generated integers\nfor a target value supplied "
54: "by the user, and then reports a position where\nthe "
55: "target value was found, or that the target value was not "
56: "present.\n\n";
57: Pause();
59: vector<int> v; //Sequence of integer values to be searched
60: int numberOfInts; //Number of integer values in search sequence
61: int low, high; //Range of values in search sequence
63: ReadInt("Enter number of integers to search through: ", numberOfInts);
64: ReadInt("Enter lower bound of search range: ", low);
65: ReadInt("Enter upper bound of search range: ", high);
66: for (int i=1; i<=numberOfInts; i++)
67: v.push_back(rangen.getNextInt(low, high));
69: const string SORT_QUERY =
70: "\nIf you are going to use binary search, the values "
71: "will have to be sorted.\nSort the values?";
72: if (userSaysYes(SORT_QUERY)) sort(v.begin(), v.end());
74: const string CONTINUE_QUERY =
75: "Would you like to search for another target value?";
76: do
77: {
78: timer_ON = userSaysYes("Time the search?");
79: counter_ON = userSaysYes("Count the operations?");
80: DisplayValues(v);
81: Search(v);
82: if (timer_ON || counter_ON) DisplayStatistics();
83: DisplayValues(v);
84: } while (userSaysYes(CONTINUE_QUERY));
85: }
88: void DisplayValues
89: (
90: const vector<int>& v //in
91: )
92: //Pre: v has been initialized.
93: //Post: The integer values in v have been displayed, 10 per line.
94: {
95: cout << "\nHere is the current list of integer values:\n";
96: const int NUMBER_PER_LINE = 10;
97: int i;
98: for (i = 0; i < (int)v.size(); i++)
99: {
100: cout << setw(6) << v.at(i);
101: if ((i+1) % NUMBER_PER_LINE == 0) cout << endl;
102: }
103: cout << ((i % NUMBER_PER_LINE == 0) ? "\n" : "\n\n");
104: }
107: void DisplayStatistics()
108: /*Pre:
109: The following global objects and variables have been declared:
110: - timer, an object of the Stopwatch class
111: - timer_ON, a "switch" variable of type bool
112: - counter, an object of the OperationCounter class
113: - counter_ON, a "switch" variable of type bool
114: /*Post:
115: If counter_ON is true, the number of assignments, comparisons,
116: exchanges and (if applicable) the "other" operation recorded by
117: counter are displayed in summary form. And, if timer_ON is true,
118: the time taken by the algorithm is displayed. If neither counter_ON
119: nor timer_ON is true, the function does nothing (except provide a
120: pause if actually called).
121: */
122: {
123: if (counter_ON) counter.displayAllCounts();
124: if (timer_ON) cout << "Time taken = " << timer.getSeconds()
125: << " seconds.\n\n";
126: Pause();
127: }
130: void Search(/* in */ vector<int>& v)
132: //Pre: v has been initialized.
133: //Post: A search for some value in v has been performed.
134: {
135: int targetValue;
136: ReadInt("What value would you like to search for? ", targetValue);
138: cout << "Between what two positions would you like to search?\n";
139: int firstPosition, lastPosition;
140: ReadInt("Enter first position here: ", firstPosition);
141: ReadInt("Enter last position here: ", lastPosition);
143: char sortChoice;
144: ReadChar("\nYou may have a choice of linear or binary search, "
145: "but ...\nif you did not sort the list, you can only "
146: "use linear search.\nWhich would you like to use? (L/B) ",
147: sortChoice);
149: bool targetFound;
150: int targetPosition;
151: switch (sortChoice)
152: {
153: case 'L':
154: case 'l':
155: if (timer_ON) timer.start();
156: SearchLinear(v, targetValue, firstPosition, lastPosition,
157: targetPosition, targetFound);
158: if (timer_ON) timer.stop();
159: break;
161: case 'B':
162: case 'b':
163: if (timer_ON) timer.start();
164: SearchBinary(v, targetValue, firstPosition, lastPosition,
165: targetPosition, targetFound);
166: if (timer_ON) timer.stop();
167: break;
168: }
170: cout << endl << targetValue;
171: if (targetFound)
172: cout << " located at position " << targetPosition << ".\n\n";
173: else
174: cout << " not found.\n\n";
175: Pause();
176: }
179: void SearchLinear(/* in */ const vector<int>& v,
180: /* in */ int targetValue,
181: /* in */ int firstPosition,
182: /* in */ int lastPosition,
183: /* out */ int& targetPosition,
184: /* out */ bool& targetFound)
185: /*Pre:
186: v, targetValue, firstPosition and lastPosition have been initialized.
187: 1 <= firstPosition <= lastPosition <= v.size().
188: /*Post:
189: Either targetFound == true and targetValue is located at position
190: targetPosition (i.e., at v[targetPosition-1]), or targetFound == false
191: and targetPosition == lastPostion+1. Note that in this latter case
192: targetPosition must not be used.
193: */
194: {
195: if (counter_ON) counter.reset();
197: int index = firstPosition-1;
198: //while (targetValue != v.at(index) && index <= lastPosition-1)
199: //Show that the above replacement for the line below does not
200: //work in all cases and explain where and why things go wrong.
201: while (index <= lastPosition-1 && targetValue != v.at(index))
202: {
203: ++index;
204: if (timer_ON) timer.delay(10);
205: if (counter_ON) counter.incrementComparisons();
206: }
208: if (timer_ON) timer.delay(10);
209: if (index < lastPosition) counter.incrementComparisons();
210: //Since if the target value is found, the value comparison
211: //in the while-condition is not counted in the loop body.
213: targetFound = (index < lastPosition);
214: targetPosition = index+1;
215: }
217: /*Here is the essential code of the algorithm, repeated for clarity:
218: ====================================================================
219: int index = firstPosition-1;
220: while (index <= lastPosition-1 && targetValue != v.at(index))
221: ++index;
222: targetFound = (index < lastPosition);
223: targetPosition = index+1;
224: */
226: void SearchBinary(/* in */ const vector<int>& v,
227: /* in */ int targetValue,
228: /* in */ int firstPosition,
229: /* in */ int lastPosition,
230: /* out */ int& targetPosition,
231: /* out */ bool& targetFound)
232: /*Pre:
233: v, targetValue, firstPosition and lastPosition have been initialized.
234: 1 <= firstPosition <= lastPosition <= v.size() and the values in v must
235: be sorted.
236: /*Post:
237: Either targetFound == true and targetValue is located at targetPosition,
238: (i.e., at v[targetPosition-1]), or targetFound == false and targetPosition
239: is undefined.
240: */
241: {
242: if (counter_ON) counter.reset();
244: int lowIndex = firstPosition-1;
245: int highIndex = lastPosition-1;
246: int middleIndex;
248: targetFound = false;
249: while (highIndex >= lowIndex && !targetFound)
250: {
251: middleIndex = (lowIndex + highIndex)/2;
252: if (targetValue < v.at(middleIndex))
253: {
254: highIndex = middleIndex - 1;
255: if (timer_ON) timer.delay(10);
256: if (counter_ON) counter.incrementComparisons();
257: }
258: else if (targetValue > v.at(middleIndex))
259: {
260: lowIndex = middleIndex + 1;
261: if (timer_ON) timer.delay(10);
262: if (counter_ON) counter.incrementComparisons(2);
263: }
264: else
265: {
266: targetFound = true;
267: if (timer_ON) timer.delay(20);
268: if (counter_ON) counter.incrementComparisons(2);
269: }
270: }
271: targetPosition = middleIndex+1;
272: }
274: /*Here is the essential code of the algorithm, repeated for clarity:
275: ====================================================================
276: int lowIndex = firstPosition-1;
277: int highIndex = lastPosition-1;
278: int middleIndex;
280: targetFound = false;
281: while (highIndex >= lowIndex && !targetFound)
282: {
283: middleIndex = (lowIndex + highIndex)/2;
284: if (targetValue < v.at(middleIndex))
285: highIndex = middleIndex - 1;
286: else if (targetValue > v.at(middleIndex))
287: lowIndex = middleIndex + 1;
288: else
289: targetFound = true;
290: }
291: targetPosition = middleIndex+1;
292: */