1: /** @file profiler_search_binary.cpp
2: Perform timing and operation counts for binary searches.
3: */
5: #include <iostream>
6: #include <iomanip>
7: #include <string>
8: #include <algorithm>
9: #include <vector>
10: using namespace std;
12: #include "utilities.h"
13: using Scobey::Pause;
14: using Scobey::ReadInt;
15: using Scobey::userSaysYes;
16: using Scobey::OperationCounter;
17: using Scobey::RandomGenerator;
18: using Scobey::Stopwatch;
20: //Global variables permitted
21: //These global variables are permissible for the following reasons:
22: //There is only one of each used throughout the program and each is used
23: //in the same way each time it is used, much like the "global object" cout
24: //is used everywhere throughout a program to display output on the screen.
25: OperationCounter counter;
26: Stopwatch timer;
27: bool counter_ON = false;
28: bool timer_ON = false;
31: //Function prototypes
32: void Search
33: (
34: vector<int>& v //in
35: );
36: /**<
37: Handle the high-level interaction with the user for each search.
38: @param v The current vector of integer values through which to search.
39: @pre v has been initialized.
40: @post A search for some value in v has been performed.
41: */
44: void SearchBinary
45: (
46: const vector<int>& v, //in
47: int targetValue, //in
48: int firstPosition, //in
49: int lastPosition, //in
50: int& targetPosition, //out
51: bool& targetFound //out
52: );
53: /**<
54: Perform a search for a target value in the vector of integers.
55: @param v The current vector of integers through which to search.
56: @param targetValue The value for which to search.
57: @param firstPosition The first postion of the range to search.
58: @param lastPosition The last position of the range to search.
59: @param targetPosition The position where the target value was found.
60: @param targetFound Indicates if the target was found.
61: @pre v, targetValue, firstPosition and lastPosition have been initialized.
62: It must also be true that 1 <= firstPosition <= lastPosition <= v.size().
63: @post Either targetFound == true and targetValue is located at position
64: targetPosition (i.e., at v[targetPosition-1]), or targetFound == false
65: and targetPosition == lastPostion+1. Note that in this latter case
66: targetPosition must not be used.
67: */
70: void DisplayValues
71: (
72: const vector<int>& v //in
73: );
74: /**<
75: Display the sequence of integers through which the searches will
76: be performed.
77: @param v The current vector of integers through which to search.
78: @pre v has been initialized.
79: @post The integer values in v have been displayed, 10 per line.
80: */
83: void DisplayStatistics();
84: /**<
85: Display results of comparison counting and timing if these actions
86: have been performed.
87: @pre The following global objects and variables have been declared:
88: - timer, an object of the Stopwatch class
89: - timer_ON, a "switch" variable of type bool
90: - counter, an object of the OperationCounter class
91: - counter_ON, a "switch" variable of type bool
92: @post If counter_ON is true, the number of comparisons recorded by
93: counter are displayed in summary form. And, if timer_ON is true,
94: the time taken by the algorithm is displayed. If neither counter_ON
95: nor timer_ON is true, the function does nothing (except provide a
96: pause if actually called).
97: */
100: int main()
101: {
102: cout << "\nThis program is a \"search profiler\". It uses a binary "
103: "search algorithm to\nsearch through a sorted sequence of "
104: "integers for a target value supplied\nby the user, and then "
105: "reports the first position where the target value was\nfound, or "
106: "that the target value was not present. It can also time a search"
107: "\nand/or count the number of comparisons performed."
108:
109: "\n\nAll values may be displayed, if the user so wishes. "
110: "They are shown 10 per\nline, with each value right-justified "
111: "within a fieldwidth of 7 spaces. Thus\neach generated value, "
112: "including the minus sign, if any, should not occupy\nmore than "
113: "6 spaces.\n";
114: Pause();
116: vector<int> v; //Sequence of integer values to be searched
117: int numberOfInts; //Number of integer values in search sequence
118: int low, high; //Range of values in search sequence
120: ReadInt("Enter required number of integers for the sequence to "
121: "be searched: ", numberOfInts);
122: ReadInt("Enter lower bound for that sequence: ", low);
123: ReadInt("Enter upper bound for that sequence: ", high);
124: RandomGenerator g;
125: if (userSaysYes("Would you like to \"seed\" the random generator?"))
126: {
127: int seedValue;
128: ReadInt("What seed value would you like to use? ", seedValue);
129: g.reset(seedValue);
130: }
131: for (int i=1; i<=numberOfInts; i++)
132: v.push_back(g.getNextInt(low, high));
133: sort(v.begin(), v.end());
135: const string CONTINUE_QUERY =
136: "Would you like to search for another target value?";
137: do
138: {
139: if (userSaysYes("Display the values?"))
140: DisplayValues(v);
141: timer_ON = userSaysYes("Time the search?");
142: counter_ON = userSaysYes("Count the operations?");
143: Search(v);
144: if (timer_ON || counter_ON) DisplayStatistics();
145: }
146: while (userSaysYes(CONTINUE_QUERY));
147: }
150: void DisplayValues
151: (
152: const vector<int>& v //in
153: )
154: {
155: cout << "\nHere is the current list of integer values:\n";
156: const int NUMBER_PER_LINE = 10;
157: vector<int>::size_type i;
158: for (i=0; i<v.size(); i++)
159: {
160: cout << setw(7) << v.at(i);
161: if ((i+1) % NUMBER_PER_LINE == 0) cout << endl;
162: }
163: //Note that the value of i in the following is the same as
164: //the last value of i+1 in the body of the above loop.
165: cout << ((i % NUMBER_PER_LINE == 0) ? "\n" : "\n\n");
166: }
169: void DisplayStatistics()
170: {
171: if (counter_ON) counter.displayAllCounts();
172: if (timer_ON) cout << "Time taken = " << timer.getSeconds()
173: << " seconds.\n\n";
174: Pause();
175: }
178: void Search
179: (
180: vector<int>& v //in
181: )
182: {
183: int targetValue;
184: ReadInt("\nFor what value would you like to search? ", targetValue);
186: cout << "Between what two positions would you like to search?\n";
187: int firstPosition, lastPosition;
188: ReadInt("Enter first position here: ", firstPosition);
189: ReadInt("Enter last position here: ", lastPosition);
191: bool targetFound;
192: int targetPosition;
193: if (timer_ON) timer.start();
194: SearchBinary(v, targetValue, firstPosition, lastPosition,
195: targetPosition, targetFound);
196: if (timer_ON) timer.stop();
198: cout << "\nValue " << targetValue;
199: if (targetFound)
200: cout << " located at position " << targetPosition << ".\n";
201: else
202: cout << " not found.\n";
203: Pause();
204: }
207: void SearchBinary
208: (
209: const vector<int>& v, //in
210: int targetValue, //in
211: int firstPosition, //in
212: int lastPosition, //in
213: int& targetPosition, //out
214: bool& targetFound //out
215: )
216: {
217: if (counter_ON) counter.reset();
219: int lowIndex = firstPosition-1;
220: int highIndex = lastPosition-1;
221: int middleIndex;
223: targetFound = false;
224: while (highIndex >= lowIndex && !targetFound)
225: {
226: middleIndex = (lowIndex + highIndex)/2;
227: if (targetValue < v.at(middleIndex))
228: {
229: highIndex = middleIndex - 1;
230: if (timer_ON) timer.delay(10);
231: if (counter_ON) counter.incrementComparisons();
232: }
233: else if (targetValue > v.at(middleIndex))
234: {
235: lowIndex = middleIndex + 1;
236: if (timer_ON) timer.delay(20);
237: if (counter_ON) counter.incrementComparisons(2);
238: }
239: else
240: {
241: targetFound = true;
242: if (timer_ON) timer.delay(20);
243: if (counter_ON) counter.incrementComparisons(2);
244: }
245: }
246: targetPosition = middleIndex+1;
247: }
249: /*Here is the essential code of the algorithm, repeated for clarity:
250: ====================================================================
251: int lowIndex = firstPosition-1;
252: int highIndex = lastPosition-1;
253: int middleIndex;
255: targetFound = false;
256: while (highIndex >= lowIndex && !targetFound)
257: {
258: middleIndex = (lowIndex + highIndex)/2;
259: if (targetValue < v.at(middleIndex))
260: highIndex = middleIndex - 1;
261: else if (targetValue > v.at(middleIndex))
262: lowIndex = middleIndex + 1;
263: else
264: targetFound = true;
265: }
266: targetPosition = middleIndex+1;
267: */