1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
#include <iostream>
#include <iomanip>
using namespace std;
int main();
// Function prototypes
void ticketSort(int [], int);
int linearSearch(const int [], int, int);
int binarySearch(const int [], int, int);
const int SIZE = 10;
int main()
{
int tickets[SIZE] = { 13579, 62483, 26791, 77777, 26792,
79422, 33445, 85647, 55555, 93121 };
int winningNumber; // To hold the winning number entered
int linearResult; // To hold the result from linear search
int binaryResult; // To hold the result from binary search
cout << "Enter this week's winning 5-digit number: ";
cin >> winningNumber;
// Sort the array in ascending order
ticketSort(tickets, SIZE);
// Perform linear search to array for winning ticket number
linearResult = linearSearch(tickets, SIZE, winningNumber);
// Perform binary search to array for winning ticket number
binaryResult = binarySearch(tickets, SIZE, winningNumber);
// If linearSearch return -1, not a winner
if (linearResult == -1)
{
cout << "I'm sorry. You are not a winner this week.\n";
}
else
{
// Otherwise we have a winning lotto ticket
cout << "CONGRATULATIONS! Your linear search came back positive!\n";
}
// If binarySearch return -1, then not a winner
if (linearResult == -1 || binaryResult == -1)
{
cout << "Please try again next week.\n";
}
else
{
// Otherwise we have a winning lotto ticket
cout << "CONGRATULATIONS! Your binary search came back positive!\n";
cout << "You have won this week's lottery!\n";
}
system("pause");
return 0;
}
// ***
// Definition of function ticketSort
// This function performs an ascending order bubble sort on
// the tickets array. SIZE is the number of elements in the array
// This is required for the function binarySearch to work properly
// ***
void ticketSort(int tickets[], int SIZE)
{
bool swap;
int temp;
do
{
swap = false;
for (int count = 0; count < (SIZE - 1); count++)
{
if (tickets[count] > tickets[count + 1])
{
temp = tickets[count];
tickets[count] = tickets[count + 1];
tickets[count + 1] = temp;
swap = true;
}
}
} while (swap);
}
// ***
// Definition of function linearSearch
// This function performs a linear search on
// the tickets array. SIZE is the number of elements in the array
// ***
int linearSearch(const int tickets[], int SIZE, int winningNumber)
{
int index = 0; // Used as a subscript to linear search array
int position = -1; // To record position of the search value
bool found = false; // Flag to indicate if the value was found
while (index < SIZE && !found)
{
if (tickets[index] == winningNumber) // If the value is found
{
found = true; // Set the flag
position = index; // Record the value's subscript
}
index++; // Go to the next element in the array
}
return position; // Return the position, or -1
}
// ***
// Definition of function binarySearch
// This function performs a binary search on
// the tickets array. SIZE is the number of elements in the array
// ***
int binarySearch(const int tickets[], int SIZE, int winningNumber)
{
int first = 0, // First array element
last = SIZE - 1, // Last array element
middle, // Midpoint of search
position = -1; // Position of search value
bool found = false; // Flag
while (!found && first <= last);
{
middle = (first + last) / 2; // Calculate midpoint
if (tickets[middle] == winningNumber) //If winning number found at midpoint
{
found = true;
position = middle;
}
else if (tickets[middle] > winningNumber) // If value is in lower half of tickets
last = middle - 1;
else
first = middle + 1; // If value is in upper half of tickets
}
return position;
}
|
