/* program to illustrate linear sort and binary search*/
#include <iostream>
using namespace std;

const int MAXSIZE =100;

/* Function Prototypes */
void linearsort(int [], int);
void printarray(int [], int);
int binarysearch(int [], int, int);

int main()
{
    int numb[MAXSIZE];
    int n;
    int searchvalue,position;

    cout << "Enter the number of elements in the array: " << endl;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cout << "Enter a number into the array: ";
        cin >> numb[i];
    }
    cout << endl << "Original Data" << endl;
    printarray(numb,n);

    linearsort(numb,n);

    cout << endl << "Sorted Data" << endl;
    printarray(numb,n);

    cout << endl << "Enter a search value: ";
    cin >> searchvalue;
    position = binarysearch(numb,n,searchvalue);
    if (position != -1)
        cout << searchvalue << " found in position " << position << endl;
    else
        cout << searchvalue << " not found" << endl;

//  system("pause");                        //un-comment when using DevC++
    return 0;
}

/* Function to print an array */
void printarray(int numb[], int n)
{
    for (int i = 0; i < n; i++)
        cout << numb[i] << endl;
    return;
}

/* Function linearsort()
 * Input:
 *  numb - array to be sorted
 *  n - number of elements to sort
 * Process:
 *  linear sort
 * Output:
 *  numb sorted into ascending order
 */
void linearsort(int numb[], int n)
{
    int temp;

    for (int pos = 0; pos < (n-1); pos++)
        for (int cand = (pos+1); cand < n; cand++)
            if (numb[pos] > numb[cand])
            {
                temp = numb[pos];
                numb[pos] = numb[cand];
                numb[cand] = temp;
            }
    return;
}

/* Function binarysearch()
 * Input:
 *  numb - array to be searched
 *  n - number of elements in the array
 *  searchvalue - the value to search for
 * Process:
 *  binary search
 * Output:
 *  returns the position of searchvalue in the array
 *  returns -1 if searchvalue not found
 */
int binarysearch(int numb[], int n, int searchvalue)
{
    int low,high,test;

    low = 0;
    high = n - 1;
    while (low <= high) {
        test = (low + high) / 2;
        if (numb[test] == searchvalue)
            return (test);                  // search value found
        else if (numb[test] > searchvalue)
            high = test - 1;
        else
            low = test + 1;
    }
    return (-1);                            // search value not found
}