//OrinTill Qimid CS1A Chapter 4, P. 294, 10
//
/**************************************************************
 * Lotery ticket
 * 
 * ____________________________________________________________
 * This program will tell the user if he won the lotery or not.
 * ____________________________________________________________
 * INPUT
 * ticket   : The user ticket
 * OUTPUT
 * If the user won or lost the ticket.
 **************************************************************/
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const int SIZE=10;
bool binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    int mid;

    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 main() 
{  
    bool found;
    found = false;
    int ticket;
    int validNums[SIZE] = {13579, 26791, 26792, 33445, 55555,
    62483, 77777, 79422, 85647, 93121};
    cout<<"Whats your ticket number?"<<endl;
    cin>>ticket;
    found = binarySearch(validNums, SIZE, ticket);
    if (found == true)
    {
        cout<<"Congrats on winning!!"<<endl;
    }
    else
    {
        cout<<"Sorry u did not win the ticket"<<endl;
    }
    

    return 0 ;
   }