#include <iostream>
#include <vector>

const int KEY_NOT_FOUND = -1;

/* Binary search
 * It finds the key in the vector<int>
 */
int BinarySearch(const std::vector <int>* array, int first_index, int last_index, const int key) {
    while (first_index <= last_index)   {
        int middle_index = first_index + (last_index - first_index) / 2;

        if (array->at(middle_index) > key) {
            last_index = middle_index - 1;
        }
        else if (array->at(middle_index) < key) {
            first_index = middle_index + 1;
        }
        else {
            return middle_index;
        }
    }
    return KEY_NOT_FOUND;
}

/* Recursive function for a binary search
 * It finds the key in the vector<int>
 */
int RecursiveBinarySearch(const std::vector <int>* array, const int first_index, const int last_index, const int key) {
    if (first_index == last_index) {
        if (key == array->at(first_index)) {
            return first_index;
        }
        else {
            return KEY_NOT_FOUND;
        }
    }
    else {
        int middle_index = first_index + (last_index - first_index) / 2;
        if (key == array->at(middle_index)) {
            return middle_index;
        }
        else {
            if (key < array->at(middle_index)) {
                RecursiveBinarySearch(array, first_index, middle_index - 1, key);
            }
            else {
                RecursiveBinarySearch(array, middle_index + 1, last_index, key);
            }
        }
    }
}

/* QuickSort first divides a large array into two smaller sub-array:
 * the low elements and the high elements.
 * QuickSort can then recursively sort the sub-arrays.
*/
void QuickSort(std::vector <int>* array, const int first_index, const int last_index) {
    int left_index = first_index;
    int right_index = last_index;
    int pivot = array->at((first_index + last_index) / 2);

    while (left_index <= right_index) {
        while (array->at(left_index) < pivot) {
            ++left_index;
        }
        while (array->at(right_index) > pivot) {
            --right_index;
        }
        if (left_index <= right_index) {
            std::swap(array->at(left_index), array->at(right_index));
            ++left_index;
            --right_index;
        }
    }

    if (first_index < right_index) {
        QuickSort(array, first_index, right_index);
    }
    if (left_index < last_index) {
        QuickSort(array, left_index, last_index);
    }
}

int main()
{
    return 0;
}