#include <iostream>

using namespace std;

void print_array(int a[],int size)
{
    for (int i=0; i<size; i++)
        cout << a[i] << endl;
    cout << endl;
}

void myswap(int &a, int &b)
{
    int temp;

    temp=a;
    a=b;
    b=temp;
};
void bubbleSort(int a[], int size)

{
    bool swapped=false;
    int temp;

    do
    {
        swapped=false;
        // Go through all the elements except the very last element.
        for(int i=0; i<size-1; i++)
        {
            // If the 2 elements are out of order, swap them.
            if(a[i]>a[i+1])
            {
                myswap(a[i],a[i+1]);
                swapped=true;
            }
        }
    }
    while(swapped);
}

int binarySearch(int a[], int size, int key) {
    int location=-1;

    // Searching range.
    int low=0, high=size-1;

    // Item to select.
    int selection=0;

    // Was the key found in the array.
    bool found=false;

    // First must be sorted.
    bubbleSort(a,size);

    print_array(a,5);

    cout << "Searching..." << endl;

    while(!found && low<=high) {
        selection=(low+high)/2;
        cout << selection << endl;

        if(a[selection]==key) {
            found=true;

        }

        // Look for a higher number
        if(key>a[selection]) {
            low=selection+1;
        }

        // Look for a lower number.
        else if(key<a[selection]) {
            high=selection-1;
        }
    }

    if(found)
        return selection;
    else return -1;

}

int linearSearch(int a[], int size, int key) {
    int location=-1;

    for(int i=0;i<size;i++) {
        if(key==a[i]) {
            location=i;
            break;
        }
    }
    return location;
}

int main()
{
    int a[5]= {5,3,15,10,8};
    int found=0;
    print_array(a,5);
    found=binarySearch(a,5,10);
    cout << "Found at: " << found << endl;


}