#include <iostream>
#include <string>

using namespace std;

// Linear search will return the index position for
// the value search for in the array.
// If not found, -1 is returbed.
int linear_search(int array[], int size, int value);


int linear_search(int array[], int size, int value){
    // Set the location where the value is found.
    // Default location is a "not found" position.
    int location=-1;

    // Search for the value at all the positions in the array.
    for(int i=0; i<size; i++) {
        // Check if the value is in the array.
        if(array[i]==value) {
            location=i;
            // Stop searching.
            break;
        }
    }

    // Search complete.
    return location;
}

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

void linear_sort(int array[], int size){
    int lowest;

    // For all the items in the array.
    for(int position=0;position<size;position++) {
        // The lowest position in the array.
        lowest=position;

        // Compare to the remaining items to see if any are lower.
        for(int remaining=position+1;remaining<size;remaining++){
            if(array[remaining]<array[lowest])
                lowest=remaining;
        }

        // Swap the values to get the lest value at the correct position.
        myswap(array[position],array[lowest]);
    }
}

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

void bubble_sort(int array[], int size){
    bool swapped=false;

    do{
        // Reset swapped flag.
        swapped=false;

        // Check all the items in the array.
        // Comparing one to the next neighbor.
        for(int i=0;i<size-1;i++){
            // If the items are in the wrong order, swap them.
            if(array[i]>array[i+1]) {
                myswap(array[i],array[i+1]);
                swapped=true;
            }
        }

    }while(swapped);

}


// array is array to search
// size is the size of the array.
// value is the value to search for.
//
// Returns the poisition of the value in the array.
// -1 is returned if the value is not found.
int mybinary_search(int array[],int size, int value) {
    // First make sure the array's values are sorted.
    bubble_sort(array,size);

    // Range points.
    int low, high, mid;

    low=0;
    high=size-1;

    // Searches
    while(high>=low) {
        mid=(low+high)/2;

        // Value is found
        if(value==array[mid])
            return mid;
        // if midpoint value is too low.
        else if(value>array[mid])
            low=mid+1;
        // if midpoint value is too high.
        else if(value<array[mid])
            high=mid-1;
    }

    // If this point is reached, the value is not found.
    return -1;
}

int main() {
    int numbers[]={8,10,15,6,20};
    int size=5;
    int found;

    found=mybinary_search(numbers,5,20);
    cout << found << endl;

    found=mybinary_search(numbers,5,8);
    cout << found << endl;

    return 0;
}