#include <iostream>
using namespace std;

int search (int a[], int first, int last, int item)
{
       while (first <= last)
       {
             int mid = (first+last)/2;
             if ( a[mid] == item)
                 return mid;
             else if (a[mid] > item)
                last = mid -1;
             else
                first = mid + 1;
       } //end while
       return -1;
}//end search
       
              

int main()
{
    const int N = 100;
    int a[N];
    int item;
    srand(time(0));
    
    //initialize the  array with 100 sorted numbers
    a[0] = rand()%4;
    for (int i = 1; i < N; i++)
       a[i] = a[i-1] + rand()%4;
       
    cout <<"Enter item to search: ";
    cin >>item;
    int loc = search(a, 0, N-1, item);
    if (loc >= 0 )
        cout << "Item found in location: " << loc <<endl;
    else
        cout <<"Not Found" <<endl;  
    
    system("pause");
    return 0; // indicate successful termination
} // end main