/*

EE5C programming assignment 6.2

file	:	p6-2.c
compiler: 	g++
name	:	Cedric F. Lam
		Duy Nguyen (modified to C++)
S.I.D.	:	911-911-911
date	:	11-21-96
class	:	EE5C (Lect1)

*/

#include <iostream.h>
#include <stdlib.h>
#include <fstream.h>


/* Function Prototypes */
int b_search(const double*, int, double);
void print_array(double*, int);
void intro(void);

/*
 * This function implements the binary search algorithm. It returns the index
 * of the key if it is found in the list or -1 if key is not found.
 */
int b_search(const double list[], int size, /* input list and its size */
		     double key) /* item to search */
{
	int top = size -1,
	    bottom = 0,
	    mid; 
	
	while (top >= bottom){
		mid = (top + bottom)/2;
		if(list[mid] == key)  /* key found */
			return mid;
		else if(list[mid] > key)
			top = mid-1;
		else
			bottom = mid+1;
	}
	/* key not found */
	return -1;
}

/*
 * This function displays the content of the result array. 
 * A new line is started every 8 elements.
 */
void print_array(double array[], int size)
{
	int i;
	
	for(i = 0; i < size; i++){
		cout << array[i] << " ";
		if((i+1)%8 == 0) /* start a new line every 8 elements */
			cout << "\n";
	}
	cout << "\n";
}


/*
 * Introduction
 */
void intro(void)
{
	cout << "This program implememts the binary search algorithm for \n";
	cout << "a list of double precision floating point numbers.\n"; 
	cout << "The list is hard coded in the driver function.\n";
	cout << "\n";
}
		
#define SIZE 5
/* 
 * Driver program to test the b_search funtion. 
 */
int main(void)
{
	double array[SIZE] = {-10.5, -1.8, 3.5, 6.3, 7.2},
		   key;
	int index, size, i;
	char next = 'N', ch;
	ifstream ifp;
	char filename[12];
	

	intro(); /* Notes to the students. */


	cout << "Enter data filename: ";
	cin.getline(filename, 12);

	ifp.open(filename, ios::in);

	if (!ifp)
	{
		cout << "Error opening file.\n";
		exit(1);
	}

	ifp >> size;

	for (i = 0;i < size;i++)
		ifp >> array[i];

	ifp.close();
	
	cout << "List:\n"; /* Display list */	
	print_array(array, SIZE);

	do{
		/* Here is a simple input validation. */
		cout << "\nInput the item to search: ";
		cin >> key;
		
		index = b_search(array, SIZE, key);
		if(index < 0)
			cout << "Key " << key << " was not found in list.\n";
		else
			cout << "Key " << key << " was found at position " << index; 
		cout << endl;
		
		cout << "Continue (Y/N)? ";
		cin >> next;
	}while(next=='Y' || next=='y');
	
    return 0;
}