// Example 1-13 Binary search

#include <iostream>
#include <cstdlib>
using namespace std;

void fillArrayWithRandomNumbers(int a[], int size);
void print(int a[], int size);
void sort(int a[], int size);
void swap(int& a, int& b);
int search(int searchValue, int a[], int size);

int main()
{
    int array[100];
    int number;
    int size = sizeof(array) / sizeof(int);
    fillArrayWithRandomNumbers(array, size);
    sort(array,size);
    print(array,size);

    while (1)
    {
        cout << "What number do you want to search for (0 to exit)? ";
        cin >> number;
        if (number == 0)
            break;
        cout << search(number,array,size) << endl;
    }

    return 0;
}

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

// selection sort
void sort (int a[], int size)
{
    int minIndex;
    for (int i = 0; i < size - 1; i++)
    {
        minIndex = i;
        for (int j = i+1; j < size; j++)
        {
            if (a[j] < a[minIndex])
            {
                minIndex = j;
            }
        }
        if(minIndex != i)
        {
            swap(a[i],a[minIndex]);
        }
    }
}

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


void fillArrayWithRandomNumbers(int a[], int size)
{
    int i;
    for (i = 0; i < size; i++)
    {
        a[i] = rand()%1000;
    }
}

// Returns array index position of searchValue
// Returns -1 if searchValue is not found
int search(int searchValue, int a[], int size)
{
    int low, high, middle;
    low = 0;
    high = size-1;

    while (low <= high)
    {
        middle = (low + high) / 2;
        if (searchValue < a[middle])
        {
            high = middle - 1;
        }
        else if (searchValue > a[middle])
        {
            low = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    // Return -1 if searchValue not found
    return -1;
}