#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

enum SearchType {
    LessThan = 0,
    LessThanEquals = 1,
    Equals = 2,
    GreaterThanEquals = 3,
    GreaterThan = 4
};

enum SearchResult {
    NotFound = 0,
    FoundExact,
    FoundGreater,
    FoundLess
};

/* This function returns the index of the element equal to greater than key */
int SearchKey(const int * const items, const int n_items, const int ascending, const int key)
{
    for(int i = (ascending? 0 : n_items-1); ascending?(i < n_items):(i>0); ascending? i++ : i--)
    {
        if (key <= items[i])
        {
            return i;
        }
    }

    return -1;
}


SearchResult Search(const int * const items,
                    const int n_items,
                    const int ascending,
                    const int key,
                    const SearchType type,
                    int* const index)
{
    int start = ascending ? 0 : n_items-1;
    int end = ascending ? n_items-1 : 0;

    *index = -1;

    switch(type)
    {
        int tempIndex;

        case LessThan:
            if(key <= items[start])
            {
               return NotFound;
            }
            else if(key > items[end])
            {
               *index = end;
               return FoundLess;
            }
            else
            {
                tempIndex = SearchKey(items, n_items, ascending, key);
                *index = (ascending) ? tempIndex - 1 : tempIndex + 1;
                return FoundLess;
            }

        case LessThanEquals:
            if(key < items[start])
            {
                return NotFound;
            }
            else if(key == items[start])
            {
                *index = start;
                return FoundExact;
            }
            else if(key > items[end])
            {
                *index = end;
                return FoundLess;
            }
            else
            {
                tempIndex = SearchKey(items, n_items, ascending, key);
                if (key == items[tempIndex])
                {
                    *index = tempIndex;
                    return FoundExact;
                }
                else
                {
                    *index = (ascending) ? tempIndex -1 : tempIndex + 1;
                    return FoundLess;
                }
            }

        case Equals:
            if (key > items[end] || key < items[start])
            {
                return NotFound;
            }
            else
            {
                tempIndex = SearchKey(items, n_items, ascending, key);
                if (key == items[tempIndex])
                {
                    *index = tempIndex;
                    return FoundExact;
                }

                return NotFound;
            }

        case GreaterThanEquals:
            if (key < items[start])
            {
                *index = start;
                return FoundGreater;
            }
            else if (key == items[start])
            {
                *index = start;
                return FoundExact;
            }
            else if (key > items[end])
            {
                return NotFound;
            }
            else if (key == items[end])
            {
                *index = end;
                return FoundExact;
            }
            else
            {
                tempIndex = SearchKey(items, n_items, ascending, key);
                *index = tempIndex;
                return (key == items[tempIndex])? FoundExact: FoundGreater;
            }

        case GreaterThan:
            if (key < items[start])
            {
                *index = start;
                return FoundGreater;
            }
            else if (key >= items[end])
            {
                return NotFound;
            }
            else
            {
                 tempIndex = SearchKey(items, n_items, ascending, key);
                 *index = (key == items[tempIndex])? (ascending?tempIndex+1:tempIndex-1) : tempIndex;
                 return FoundGreater;
            }

        default:
            return NotFound;

    }
}

/* Function returns readable string for given enum SearchResult */
const char* getSearchTypeName(SearchResult result)
{
    switch (result)
    {
        case NotFound:
            return "NotFound";

        case FoundExact:
            return "FoundExact";

        case FoundGreater:
            return "FoundGreater";

        case FoundLess:
            return "FoundLess";
    }
}

/* Function returns readable string for given enum SearchType */
const char* getTypeName(SearchType type)
{
    switch(type)
    {
        case LessThan:
            return "LessThan";

        case LessThanEquals:
            return "LessThanEquals";

        case Equals:
            return "Equals";

        case GreaterThanEquals:
            return "GreaterThanEquals";

        case GreaterThan:
            return "GreaterThan";
    }
}

void printArray(const int * const items, const int n_items)
{
    int i;
    for(i=0; i<n_items;i++)
    {
        cout << items[i] << " ";
    }
    cout << endl;
}


void printOutput(int const key, const SearchType type, const SearchResult res, int * const index)
{
    cout << key << " " << getTypeName(type) << " " << getSearchTypeName(res) << " " << (int)(*index) << endl;
}

int main()
{
    // Sample arrays for testing
    const int arr[] = {10, 8, 6, 4, 2, 0};

    // search element and type
    int key = 2;
    SearchType type = Equals;

    // If search result is NotFound, then index will be set to default value -1
    int default_index = -1;
    int* const  index = &default_index;

    // Input array length
    int arr_len = sizeof(arr)/sizeof(int);

    // Array order - Ascending or descending
    bool is_ascending = (arr[0]<arr[1]) ? 1 : 0;

    SearchResult res = Search(arr, arr_len, is_ascending, key, type, index);
    printOutput(key, type, res, index);

    return 0;
}