/* Binary Search program  */

//#include <lvp\bool.h>

/* Merge Sort program */

#include <stdlib.h>
#include <iostream.h>
#include <lvpvector.h>
#include <lvprandom.h>

using namespace std;	// October 5, 2001

typedef int ItemType;
typedef lvpvector<ItemType> ArrayType;

//--------------------------------------------------------------------------------
void Merge(ArrayType &A, int Start, int Mid, int End)
/*	Merges two sorted portions of A
	Pre: A[Start..Mid] is sorted, A[Mid+1..End] is sorted
	Start <= Mid <= End
	Post: A[Start..End] is sorted	                              */
{
	ArrayType Temp(A.length());

	int P1 = Start; int P2 = Mid+1;    // Indexes of current item in each sublist
	int Spot = Start;    // Present location in Temp
	while (!(P1>Mid && P2>End)) {
		if ((P1>Mid) || ((P2<=End) && (A[P2]<A[P1]))) {
			Temp[Spot] = A[P2];
			P2++;
		}
		else {
			Temp[Spot] = A[P1];
			P1++;
		}
		Spot++;
	}
	// Copy values from Temp back to A 
	for (int i=Start; i<=End; i++)
		A[i] = Temp[i];
}
//--------------------------------------------------------------------------------
void MergeSort(ArrayType &A, int Start, int End)
/*	Sorts A[Start..End] elements from low to high
	Pre: Start, End >= 0
	Post: Elements A[Start..End] are sorted from low to high */
{
	if (Start < End) {
		int Mid = (Start+End)/2;
		MergeSort(A, Start, Mid);
		MergeSort(A, Mid+1, End);
		Merge(A, Start, Mid, End);
	}
}
//--------------------------------------------------------------------------------
void LoadRandomArray(ArrayType &A, int Size)
/*	Fills array A with Size random values in the range 0..999 */
{
	const int MaxValue = 999;
	A.resize(Size);
	for (int i=0; i<Size; i++)
		A[i] = lvprandom(MaxValue+1);
}
//--------------------------------------------------------------------------------
void DisplayArray(const ArrayType &A)
/*	Displays the items of A, with field width of 5, 10 per line */
{
	for (int i=0; i<A.length(); i++) {
		cout.width(5); cout << A[i];
		if ((i+1)%10 == 0)
			cout << endl;
	}
	cout << endl;
}
//--------------------------------------------------------------------------------
void Sort (ArrayType &A)
/*	Sorts array A from low to high */
{
	MergeSort(A, 0, A.length()-1);
}
//--------------------------------------------------------------------------------
int BinarySearch(const ArrayType &A, int Start, int End, int Goal)
/*	Returns position of Goal, or –1 if Goal not found
	Pre: Array A[Start..End] is sorted from low to high
	Post: Position of Goal in A[Start..End] returned, or –1 if Goal not found */
{
	if (Start > End)
		return (-1);
	else {
		int Mid = (Start+End)/2;
		if (Goal == A[Mid])
			return (Mid);
		else if (Goal < A[Mid])
			return (BinarySearch(A, Start, Mid-1, Goal));
		else
			return (BinarySearch(A, Mid+1, End, Goal));
	}
}
//--------------------------------------------------------------------------------
int Search(ArrayType &A, int Goal)
/*	Searches an array for position of Goal
	Pre: Array A is sorted from low to high
	Post: Position of Goal in A returned, or –1 returned if Goal not found */
{
	return(BinarySearch(A, 0, A.length()-1, Goal));
}
//--------------------------------------------------------------------------------
int main()
{
	randomize();
	ArrayType Sample;
	const int SampleSize = 20;
	LoadRandomArray(Sample, SampleSize);
	Sort(Sample);
	DisplayArray(Sample);
	do {
		int Goal;
		cout << "Enter a number to search for (-1 = done): ";
		cin >> Goal;
		if (Goal == -1)
			break;
		cout << "Found at: " << Search(Sample,Goal) << endl;
	} while (true);
	return(0);
}