// Marvyn Jesse De La Torre CS1A Chapter 8 #3 pg.487
//
/*************************************************************
*
* Find Lottery Tickets
*
* This program uses binary search to find a number in
* a sorted array of lottery numbers.
*
* Input:
* win: The number entered by the user
*
* Output:
* Displays whether the number was found.
*************************************************************/
#include <iostream>
using namespace std;
int binary(int arr[], int size, int win);
int main()
{
int arr[] = {
13579, 26791, 26792, 33445, 55555,
62483, 77777, 79422, 85647, 93121
};
int size = sizeof(arr) / sizeof(arr[0]);
int win;
cout << "Enter the number to search for: ";
cin >> win;
int position = binary(arr, size, win);
if (position == -1)
{
cout << "Number not found." << endl;
}
else
{
cout << "Number found." << endl;
}
return 0;
}
int binary(int arr[], int size, int win)
{
int first = 0;
int last = size - 1;
int position = -1;
while (position == -1 && first <= last)
{
int middle = (first + last) / 2;
if (arr[middle] == win)
{
position = middle;
}
else if (arr[middle] > win)
{
last = middle - 1;
}
else
{
first = middle + 1;
}
}
return position;
}
Ly8gTWFydnluIEplc3NlIERlIExhIFRvcnJlICAgICAgICAgICAgQ1MxQSAgICAgQ2hhcHRlciA4ICMzIHBnLjQ4NwovLwovKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgoqCiogRmluZCBMb3R0ZXJ5IFRpY2tldHMKKgoqIFRoaXMgcHJvZ3JhbSB1c2VzIGJpbmFyeSBzZWFyY2ggdG8gZmluZCBhIG51bWJlciBpbgoqIGEgc29ydGVkIGFycmF5IG9mIGxvdHRlcnkgbnVtYmVycy4KKgoqIElucHV0OgoqICAgd2luOiBUaGUgbnVtYmVyIGVudGVyZWQgYnkgdGhlIHVzZXIKKgoqIE91dHB1dDoKKiAgIERpc3BsYXlzIHdoZXRoZXIgdGhlIG51bWJlciB3YXMgZm91bmQuCioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCgojaW5jbHVkZSA8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgYmluYXJ5KGludCBhcnJbXSwgaW50IHNpemUsIGludCB3aW4pOwoKaW50IG1haW4oKQp7CiAgICBpbnQgYXJyW10gPSB7CiAgICAgICAgMTM1NzksIDI2NzkxLCAyNjc5MiwgMzM0NDUsIDU1NTU1LAogICAgICAgIDYyNDgzLCA3Nzc3NywgNzk0MjIsIDg1NjQ3LCA5MzEyMQogICAgfTsKCiAgICBpbnQgc2l6ZSA9IHNpemVvZihhcnIpIC8gc2l6ZW9mKGFyclswXSk7CiAgICBpbnQgd2luOwoKICAgIGNvdXQgPDwgIkVudGVyIHRoZSBudW1iZXIgdG8gc2VhcmNoIGZvcjogIjsKICAgIGNpbiA+PiB3aW47CgogICAgaW50IHBvc2l0aW9uID0gYmluYXJ5KGFyciwgc2l6ZSwgd2luKTsKCiAgICBpZiAocG9zaXRpb24gPT0gLTEpCiAgICB7CiAgICAgICAgY291dCA8PCAiTnVtYmVyIG5vdCBmb3VuZC4iIDw8IGVuZGw7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgY291dCA8PCAiTnVtYmVyIGZvdW5kLiIgPDwgZW5kbDsKICAgIH0KCiAgICByZXR1cm4gMDsKfQoKaW50IGJpbmFyeShpbnQgYXJyW10sIGludCBzaXplLCBpbnQgd2luKQp7CiAgICBpbnQgZmlyc3QgPSAwOwogICAgaW50IGxhc3QgPSBzaXplIC0gMTsKICAgIGludCBwb3NpdGlvbiA9IC0xOwoKICAgIHdoaWxlIChwb3NpdGlvbiA9PSAtMSAmJiBmaXJzdCA8PSBsYXN0KQogICAgewogICAgICAgIGludCBtaWRkbGUgPSAoZmlyc3QgKyBsYXN0KSAvIDI7CgogICAgICAgIGlmIChhcnJbbWlkZGxlXSA9PSB3aW4pCiAgICAgICAgewogICAgICAgICAgICBwb3NpdGlvbiA9IG1pZGRsZTsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZiAoYXJyW21pZGRsZV0gPiB3aW4pCiAgICAgICAgewogICAgICAgICAgICBsYXN0ID0gbWlkZGxlIC0gMTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgZmlyc3QgPSBtaWRkbGUgKyAxOwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gcG9zaXRpb247Cn0=