//OrinTill Qimid CS1A Chapter 4, P. 294, 10
//
/**************************************************************
* Check guest list
*
* ____________________________________________________________
* This program will if the user name is on the list or not.
* ____________________________________________________________
* INPUT
* name: User Name
* OUTPUT
* If the user name is on the list or not.
**************************************************************/
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
bool binarySearch(string arr[], int size, string target)
{
int left;
int right;
left = 0;
right = size-1;
int mid;
//checking if the number is the first or last number.
if (arr[left].compare (target))
{
return true;
}
if (arr[right].compare (target))
{
return true;
}
while (left <= right)
{
mid = left + (right - left) / 2;
// Check if target is present at mid
if (arr[mid].compare (target))
{
return true;
}
// If target is greater, ignore the left half
else if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, ignore the right half
else {
right = mid - 1;
}
}
return false;
}
string* Sort(string arr[], int size)
{
string lowest;
int var;
for (int s = 0; s < size; s++)
{
lowest = arr[s];
var = s;
for (int i = s+1; i < size; i++)
{
if (lowest > arr[i])
{
lowest = arr[i];
var = i;
}
}
arr[var] = arr[s];
arr[s] = lowest;
}
return arr;
}
int main()
{
const int NUM_NAMES = 20;
string name;
bool found;
found = false;
cout<<"What is your name"<<endl;
cin>>name;
string names[NUM_NAMES] = {"Collins, Bill", "Smith, Bart", "Allen, Jim",
"Griffin, Jim", "Stamey, Marty", "Rose, Geri",
"Taylor, Terri", "Johnson, Jill",
"Allison, Jeff", "Looney, Joe", "Wolfe, Bill",
"James, Jean", "Weaver, Jim", "Pore, Bob",
"Rutherford, Greg", "Javens, Renee",
"Harrison, Rose", "Setzer, Cathy",
"Pike, Gordon", "Holland, Beth"};
found = binarySearch(Sort(names, NUM_NAMES), NUM_NAMES, name);
if (found == true)
{
cout<<"Your name is on the list"<<endl;
}
else
{
cout<<"Your name is not on the list"<<endl;
}
return 0 ;
}
Ly9PcmluVGlsbCBRaW1pZCBDUzFBIENoYXB0ZXIgNCwgUC4gMjk0LCAxMAovLwovKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKICogQ2hlY2sgZ3Vlc3QgbGlzdAogKiAKICogX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fCiAqIFRoaXMgcHJvZ3JhbSB3aWxsIGlmIHRoZSB1c2VyIG5hbWUgaXMgb24gdGhlIGxpc3Qgb3Igbm90LgogKiBfX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KICogSU5QVVQKICogbmFtZTogVXNlciBOYW1lCiAqIE9VVFBVVAogKiBJZiB0aGUgdXNlciBuYW1lIGlzIG9uIHRoZSBsaXN0IG9yIG5vdC4KICoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8Y21hdGg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmJvb2wgYmluYXJ5U2VhcmNoKHN0cmluZyBhcnJbXSwgaW50IHNpemUsIHN0cmluZyB0YXJnZXQpCiAgICB7CiAgICAgICAgaW50IGxlZnQ7CiAgICAgICAgaW50IHJpZ2h0OyAgCiAgICAgICAgbGVmdCA9IDA7CiAgICAgICAgcmlnaHQgPSBzaXplLTE7CiAgICAgICAgaW50IG1pZDsKICAgICAgICAvL2NoZWNraW5nIGlmIHRoZSBudW1iZXIgaXMgdGhlIGZpcnN0IG9yIGxhc3QgbnVtYmVyLgogICAgICAgIGlmIChhcnJbbGVmdF0uY29tcGFyZSAodGFyZ2V0KSkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgIH0KICAgICAgICBpZiAoYXJyW3JpZ2h0XS5jb21wYXJlICh0YXJnZXQpKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHdoaWxlIChsZWZ0IDw9IHJpZ2h0KSAKICAgICAgICB7CiAgICAgICAgbWlkID0gbGVmdCArIChyaWdodCAtIGxlZnQpIC8gMjsKICAgICAgICAKICAgICAgICAvLyBDaGVjayBpZiB0YXJnZXQgaXMgcHJlc2VudCBhdCBtaWQKICAgICAgICBpZiAoYXJyW21pZF0uY29tcGFyZSAodGFyZ2V0KSkgCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICB9CiAgICAgICAgLy8gSWYgdGFyZ2V0IGlzIGdyZWF0ZXIsIGlnbm9yZSB0aGUgbGVmdCBoYWxmCiAgICAgICAgZWxzZSBpZiAoYXJyW21pZF0gPCB0YXJnZXQpIHsKICAgICAgICAgICAgbGVmdCA9IG1pZCArIDE7CiAgICAgICAgfQogICAgICAgIC8vIElmIHRhcmdldCBpcyBzbWFsbGVyLCBpZ25vcmUgdGhlIHJpZ2h0IGhhbGYKICAgICAgICBlbHNlIHsKICAgICAgICAgICAgcmlnaHQgPSBtaWQgLSAxOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBmYWxzZTsKICAgIH0Kc3RyaW5nKiBTb3J0KHN0cmluZyBhcnJbXSwgaW50IHNpemUpCnsgCiAgICBzdHJpbmcgbG93ZXN0OwogICAgaW50IHZhcjsKICAgIAogICAgZm9yIChpbnQgcyA9IDA7IHMgPCBzaXplOyBzKyspCiAgICB7CiAgICAgICAgbG93ZXN0ID0gYXJyW3NdOwogICAgICAgIHZhciA9IHM7CiAgICAgICBmb3IgKGludCBpID0gcysxOyBpIDwgc2l6ZTsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGxvd2VzdCA+IGFycltpXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBsb3dlc3QgPSBhcnJbaV07CiAgICAgICAgICAgICAgICB2YXIgPSBpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgIH0KICAgICAgICAgYXJyW3Zhcl0gPSBhcnJbc107CiAgICAgICAgIGFycltzXSA9IGxvd2VzdDsKICAgIH0KICAgIAogICByZXR1cm4gYXJyOwogICAgCn0KaW50IG1haW4oKSAKewoKICAgIGNvbnN0IGludCBOVU1fTkFNRVMgPSAyMDsKICAgIHN0cmluZyBuYW1lOwogICAgYm9vbCBmb3VuZDsKICAgIGZvdW5kID0gZmFsc2U7CiAgICBjb3V0PDwiV2hhdCBpcyB5b3VyIG5hbWUiPDxlbmRsOwogICAgY2luPj5uYW1lOwogICAgCiAgICBzdHJpbmcgbmFtZXNbTlVNX05BTUVTXSA9IHsiQ29sbGlucywgQmlsbCIsICJTbWl0aCwgQmFydCIsICJBbGxlbiwgSmltIiwKICAgICAgICAiR3JpZmZpbiwgSmltIiwgIlN0YW1leSwgTWFydHkiLCAiUm9zZSwgR2VyaSIsCiAgICAgICAgIlRheWxvciwgVGVycmkiLCAiSm9obnNvbiwgSmlsbCIsCiAgICAgICAgIkFsbGlzb24sIEplZmYiLCAiTG9vbmV5LCBKb2UiLCAiV29sZmUsIEJpbGwiLAogICAgICAgICJKYW1lcywgSmVhbiIsICJXZWF2ZXIsIEppbSIsICJQb3JlLCBCb2IiLAogICAgICAgICJSdXRoZXJmb3JkLCBHcmVnIiwgIkphdmVucywgUmVuZWUiLAogICAgICAgICJIYXJyaXNvbiwgUm9zZSIsICJTZXR6ZXIsIENhdGh5IiwKICAgICAgICAiUGlrZSwgR29yZG9uIiwgIkhvbGxhbmQsIEJldGgifTsKICAgICAgICBmb3VuZCA9IGJpbmFyeVNlYXJjaChTb3J0KG5hbWVzLCBOVU1fTkFNRVMpLCBOVU1fTkFNRVMsIG5hbWUpOwogICAgICAgIGlmIChmb3VuZCA9PSB0cnVlKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8IllvdXIgbmFtZSBpcyBvbiB0aGUgbGlzdCI8PGVuZGw7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PCJZb3VyIG5hbWUgaXMgbm90IG9uIHRoZSBsaXN0Ijw8ZW5kbDsKICAgICAgICB9CiAgICAgICAgCiAgICAKICAgIHJldHVybiAwIDsKICAgfQ==