//OrinTill Qimid CS1A Chapter 4, P. 294, 10
//
/**************************************************************
* Search number.
*
* ____________________________________________________________
* This program will tell the user if the entered number is vaild or not.
* ____________________________________________________________
* INPUT
* user_num : user number.
* OUTPUT
* If the number entered is vaild or not.
**************************************************************/
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
bool binarySearch(int arr[], int size, int 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] == target)
{
return true;
}
if (arr[right] == target)
{
return true;
}
while (left <= right)
{
mid = left + (right - left) / 2;
// Check if target is present at mid
if (arr[mid] == 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;
}
int* Sort(int arr[], int size)
{
int lowest;
int var;
for (int s = 0; s < size; s++)
{
lowest = arr[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()
{
// Initialize the list of valid charge account numbers
const int SIZE = 18;
int user_num;
bool found = false;
int validNumbers[SIZE] = {5658845, 4520125, 7895122, 8777541, 8451277, 1302850,
8080152, 4562555, 5552012, 5050552, 7825877, 1250255,
1005231, 6545231, 3852085, 7576651, 7881200, 4581002};
cout<<"Please enter your user number."<<endl;
cin>>user_num;
found = binarySearch(Sort(validNumbers, SIZE), SIZE, user_num);
if (found == true)
{
cout<<"Your numbers are valid"<<endl;
}
else
{
cout<<"Sorry number is invaild."<<endl;
}
return 0 ;
}
Ly9PcmluVGlsbCBRaW1pZCBDUzFBIENoYXB0ZXIgNCwgUC4gMjk0LCAxMAovLwovKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKICogU2VhcmNoIG51bWJlci4KICogCiAqIF9fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fXwogKiBUaGlzIHByb2dyYW0gd2lsbCB0ZWxsIHRoZSB1c2VyIGlmIHRoZSBlbnRlcmVkIG51bWJlciBpcyB2YWlsZCBvciBub3QuCiAqIF9fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fXwogKiBJTlBVVAogKiB1c2VyX251bSAgIDogdXNlciBudW1iZXIuCiAqIE9VVFBVVAogKiBJZiB0aGUgbnVtYmVyIGVudGVyZWQgaXMgdmFpbGQgb3Igbm90LgogKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxjbWF0aD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKYm9vbCBiaW5hcnlTZWFyY2goaW50IGFycltdLCBpbnQgc2l6ZSwgaW50IHRhcmdldCkKICAgIHsKICAgIAogICAgICAgIGludCBsZWZ0OwogICAgICAgIGludCByaWdodDsKICAgICAgICBsZWZ0ID0gMDsKICAgICAgICByaWdodCA9IHNpemUtMTsKICAgICAgICBpbnQgbWlkOwogICAgICAgIC8vY2hlY2tpbmcgaWYgdGhlIG51bWJlciBpcyB0aGUgZmlyc3Qgb3IgbGFzdCBudW1iZXIuCiAgICAgICAgaWYgKGFycltsZWZ0XSA9PSB0YXJnZXQpCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICB9CiAgICAgICAgaWYgKGFycltyaWdodF0gPT0gdGFyZ2V0KQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHdoaWxlIChsZWZ0IDw9IHJpZ2h0KSAKICAgICAgICB7CiAgICAgICAgbWlkID0gbGVmdCArIChyaWdodCAtIGxlZnQpIC8gMjsKICAgICAgICAKICAgICAgICAvLyBDaGVjayBpZiB0YXJnZXQgaXMgcHJlc2VudCBhdCBtaWQKICAgICAgICBpZiAoYXJyW21pZF0gPT0gdGFyZ2V0KSAKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgIH0KICAgICAgICAvLyBJZiB0YXJnZXQgaXMgZ3JlYXRlciwgaWdub3JlIHRoZSBsZWZ0IGhhbGYKICAgICAgICBlbHNlIGlmIChhcnJbbWlkXSA8IHRhcmdldCkgewogICAgICAgICAgICBsZWZ0ID0gbWlkICsgMTsKICAgICAgICB9CiAgICAgICAgLy8gSWYgdGFyZ2V0IGlzIHNtYWxsZXIsIGlnbm9yZSB0aGUgcmlnaHQgaGFsZgogICAgICAgIGVsc2UgewogICAgICAgICAgICByaWdodCA9IG1pZCAtIDE7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGZhbHNlOwogICAgfQppbnQqIFNvcnQoaW50IGFycltdLCBpbnQgc2l6ZSkKeyAKICAgIGludCBsb3dlc3Q7CiAgICBpbnQgdmFyOwogICAgCiAgICBmb3IgKGludCBzID0gMDsgcyA8IHNpemU7IHMrKykKICAgIHsKICAgICAgICBsb3dlc3QgPSBhcnJbc107CiAgICAgICBmb3IgKGludCBpID0gcysxOyBpIDwgc2l6ZTsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGxvd2VzdCA+IGFycltpXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBsb3dlc3QgPSBhcnJbaV07CiAgICAgICAgICAgICAgICB2YXIgPSBpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgIH0KICAgICAgICAgYXJyW3Zhcl0gPSBhcnJbc107CiAgICAgICAgIGFycltzXSA9IGxvd2VzdDsKICAgICAKICAgIH0KICAgcmV0dXJuIGFycjsKICAgIAp9CmludCBtYWluKCkgCnsKICAgIC8vIEluaXRpYWxpemUgdGhlIGxpc3Qgb2YgdmFsaWQgY2hhcmdlIGFjY291bnQgbnVtYmVycwogICAgY29uc3QgaW50IFNJWkUgPSAxODsKICAgIGludCB1c2VyX251bTsKICAgIGJvb2wgZm91bmQgPSBmYWxzZTsKICAgIGludCB2YWxpZE51bWJlcnNbU0laRV0gPSB7NTY1ODg0NSwgNDUyMDEyNSwgNzg5NTEyMiwgODc3NzU0MSwgODQ1MTI3NywgMTMwMjg1MCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgODA4MDE1MiwgNDU2MjU1NSwgNTU1MjAxMiwgNTA1MDU1MiwgNzgyNTg3NywgMTI1MDI1NSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMTAwNTIzMSwgNjU0NTIzMSwgMzg1MjA4NSwgNzU3NjY1MSwgNzg4MTIwMCwgNDU4MTAwMn07CgogICAgY291dDw8IlBsZWFzZSBlbnRlciB5b3VyIHVzZXIgbnVtYmVyLiI8PGVuZGw7CiAgICBjaW4+PnVzZXJfbnVtOwogICAgZm91bmQgPSBiaW5hcnlTZWFyY2goU29ydCh2YWxpZE51bWJlcnMsIFNJWkUpLCBTSVpFLCB1c2VyX251bSk7CiAgICBpZiAoZm91bmQgPT0gdHJ1ZSkKICAgIHsKICAgICAgICBjb3V0PDwiWW91ciBudW1iZXJzIGFyZSB2YWxpZCI8PGVuZGw7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgY291dDw8IlNvcnJ5IG51bWJlciBpcyBpbnZhaWxkLiI8PGVuZGw7CiAgICB9CiAgICAKICAgIAoKICAgIHJldHVybiAwIDsKICAgfQ==