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
|
#include <iostream>
using namespace std;
int binarySearch(const int [], int, int);
int linearSearch(const int [], int, int);
const int numElems = 10;
int main()
// variables
{
int lotteryNum;
int lotteryOptions[numElems] = {13579, 62483, 26791, 77777, 26792, 79422, 33445, 85647, 55555, 93121};
lotteryNum = linearSearch(lotteryOptions, numElems, 10);
//Get the input
cout << "Please enter a five-digit number: " << endl;
cin >> lotteryNum;
if (lotteryNum == -1)
cout << "Sorry, that is not a winning number. " << endl;
else
{
cout << "Congratulations, the winning number was " << endl;
cout << (lotteryNum + 1) << endl;
}
return 0;
}
int linearSearch(const int lotteryOptions[], int numElems, int lotteryNum)
{
int index = 0;
int position = -1;
bool found = false;
while ((index < numElems) && !found)
{
if (lotteryOptions[index] == lotteryNum)
{
found = true;
position = index;
}
index++;
}
return position;
}
// Perform linear search on player's numbers
int linearSearch(const int lotteryOptions[], int numElems, int lotteryNum);
{
int index = 0; // Used as a subscript to search array
int position = −1; // To record position of search value
bool found = false; // Flag to indicate if the value was found
while (index < numElems && !found)
{
if (lotteryOptions[index] == value) // If the value is found
{
found = true; // Set the flag
position = index; // Record the value's subscript
}
index++; // Go to the next element
}
return position; // Return the position, or −1
}
// Binary search
int binarySearch(const int lotteryOptions[], int numElems, int lotteryNum);
{
int lotteryOptions[numElems] = {13579, 62483, 26791, 77777, 26792, 79422, 33445, 85647, 55555, 93121};
int lotteryNum;
//Get the input
cout << "Please enter a five-digit number: " << endl;
cin >> lotteryNum;
lotteryNum = binarySearch(lotteryOptions, numElems, 10);
if (lotteryNum == -1)
cout << "Sorry, that is not a winning number. " << endl;
else
{
cout << "Congratulations, the winning number was " << endl;
cout << (lotteryNum + 1) << endl;
}
return 0;
}
int binarySearch(const int lotteryOptions[], int numElems, int lotteryNum)
{
int first = 0,
last = numElems - 1,
middle,
position = -1;
bool found = false;
while (!found && first <= last)
{
middle = (first + last) / 2;
if (lotteryOptions[middle] == lotteryNum)
{
found = true;
position = middle;
}
else if (lotteryOptions[middle] > lotteryNum)
last = middle = 1;
else
first = middle + 1;
}
return position;
}
| |