UVa 10474 Solution - Where is The Marble

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hlw printf("Hello World\n");
#define pcs printf("CASE# %d:\n", ++cs);
using namespace std;

const int INF = 1<<29;
const int MX  = 1e5+10;

/// using LB function
/// using find() from sorted vector
/// using binary srch

int a[MX];

int main()
{
    int n,q,x,cs=0;

    while(cin>>n>>q and n and q)
    {
        pcs;
        REP(i,n) cin>>a[i];
        sort(a,a+n);

        REP(i,q)
        {
            cin>>x;
            int p = lower_bound(a, a+n, x) - a; ///*** LB Function

            if(a[p] == x)
            {
                printf("%d found at %d\n", x, p+1);
            }
            else
                printf("%d not found\n", x);
        }
    }

    return 0;
}


///** using iterator

int main()
{
    int n,q,x,cs=0;
    vector <int> vi;

    while(cin>>n>>q and n+q)
    {
        vi.clear();

        REP(i,n) cin>>x, vi.push_back(x);

        sort(ALL(vi));

        pcs;

        REP(i,q)
        {
            cin>>x;

            vector<int> :: iterator it = find(ALL(vi),x);       ///*** it to find a char

            if(it == vi.end()) printf("%d not found\n", x);     ///*** using method
            else
            {
                printf("%d found at %d\n", x, it - vi.begin()+1);   ///***  it - vectorer shuru + 1
            }
        }
    }

    return 0;
}


///** using binary search

int main()
{
    int n,q,x,cs=0;
    vector <int> a;
    while(cin>>n>>q and n and q)
    {
        a.clear();
        pcs;
        REP(i,n) cin>>a[i];
        REP(i,n) cin>>x, a.push_back(x);
        sort(ALL(a));

        REP(i,q)
        {
            cin>>x;

            int mid, lo = 0, hi = n-1, found = 0;

            while(lo <= hi)
            {
                mid = (lo+hi) / 2;
                if(x == a[mid])
                {
                    found = 1;
                    break;
                }
                else if(x > a[mid]) lo = mid + 1;
                else if(x < a[mid]) hi = mid - 1;
            }

            if(found)
            {
                while(x == a[mid]) mid--;
                printf("%d found at %d\n", x, mid+2);
            }
            else printf("%d not found\n", x);
        }
    }
    return 0;

}