Thread: Binary Search of Array

ok i have the entire code working. there is one last thing i need to do. i must use a typedef as a data record in my headerfile to gather and report performace data (the comparisons and swaps). ive never worked with typedefs before, so how could i go about implementing this?

here is some updated code:

main.c

Code:

#pragma warning(disable : 4996)
#include <stdio.h>
#include <stdlib.h>
#include "type-proto.h"

#define bool int
#define true 1
#define false 0

#define	in_filename "Prog2Data.txt"
#define out_filename "Report.txt"
#define maxsize 100

int main(int argc,char *argv[])
{	
	/* declare array */
	int ary_nbr[maxsize];

	/* declare dynamic array */
	int *dyn_ary;

	/* number to search for */
	int data_item;

	/* comps & swaps for bubble sort */
	int *comparisons = 0;
	int *swaps = 0;

	/* comps & location for binary search */
	int *bcomparisons = 0;
	int b_location = 0;

	/* comps & location for linear search */
	int *lcomparisons = 0;
	int l_location = 0;

	/* I/O pointers */
	FILE *InFile, *OutFile;

	/* error checking */
	bool file_error_flag;

	/* Open the file to read */
	file_error_flag = false;

	InFile = fopen(in_filename, "r");
	if (InFile == NULL) 
	{
		printf("Error opening \"%s\"\n\n", in_filename);
		file_error_flag = true;
	}

	/* Creates and Opens the Write File */
	OutFile = fopen(out_filename, "w");
	if (OutFile == NULL)
	{
		printf("Error opening \"%s\"\n\n", out_filename);
		file_error_flag = true;
	}

	/* error handling if any file fails to open */
	if (file_error_flag)
	{
		printf("\nProgram terminated due to FILE error!\n\n");

		/* Identify problem file and close files that are open */
		if (InFile == NULL)
			printf("Error with %s\n",in_filename);
		else
			fclose(InFile);
		if (OutFile == NULL)
			printf("Error with %s\n",out_filename);
		else
			fclose(OutFile);
	}
	else /* Files open successfully */
	{	

		/* elements catches # of actual data loaded */
		int elements = 0;

		/* runs & catches return from load function */
		elements = load(InFile, ary_nbr, maxsize);

		printf("\n\n\n\tArray loaded with %d integers!\n\n", elements);
		fprintf(OutFile, "\n\n\n\tArray loaded with %d integers!\n\n", elements);

		/* copies array into a new dynamic array */
		dyn_ary = copyarray (ary_nbr, elements);

		/* prints actual data loaded in array pre-sort */
		printtab (OutFile, dyn_ary, elements);

		printf("\n\n\tArray copied with %d integers!\n\n", elements);
		fprintf(OutFile, "\n\n\tArray copied with %d integers!\n\n", elements);

		/* BubbleSorts the array */
		sortarray (dyn_ary, elements, &comparisons, &swaps);
		
		/* prints the # of comparisons & swaps by the BS */
		printf("\tBubble sort Performance Data:\n");
		printf("\t%i comps\n", comparisons );
		printf("\t%i swaps\n\n", swaps );
		fprintf(OutFile, "\tBubble sort Performance Data:\n");
		fprintf(OutFile, "\t%i comps\n", comparisons );
		fprintf(OutFile, "\t%i swaps\n\n", swaps );

		/* prints sorted data */
		printtab (OutFile, dyn_ary, elements);

		/* for readability */
		fprintf(OutFile, "\n");

		do
		{
			/*  user-defined variable */
			data_item = 0;

			/* prompts user for data to search for */
			printf("\n\n\tEnter the data to search for: ");
			scanf("%d", &data_item);

			/* user may only search for positive integers */
			if (data_item >= 0)
			{

				/* searches sorted array & un-sorted array */
				l_location = lsearch(ary_nbr, data_item, elements, &lcomparisons);
				b_location = binarysearch(dyn_ary, data_item, elements, &bcomparisons);
	
				/* prints search results */
				printf("\tLinear Search for %4i found at location [%2d] with %2d comps!\n", data_item, l_location, lcomparisons);
				printf("\tBinary Search for %4i found at location [%2d] with %2d comps!", data_item, b_location, bcomparisons);
				fprintf(OutFile, "\n\tLinear Search for %4i found at location [%2d] with %2d comps!", data_item, l_location, lcomparisons);
				fprintf(OutFile, "\n\tBinary Search for %4i found at location [%2d] with %2d comps!", data_item, b_location, bcomparisons);

				/* resets comparisons */
				bcomparisons = 0;
				lcomparisons = 0;
			}
			else
			{
				printf("\n\tYou entered a negative number - program will now terminate!\n\n\t");
			}
		} while (data_item >= 0); /* program continues, unless negative number is given */
	
			/* close files */
			fclose(InFile);
			fclose(OutFile);
	}	

		/* else file_error_flag */
		return file_error_flag;
}

bodies.c

Code:

#include <stdio.h>
#include <stdlib.h>
#include "type-proto.h"

/* loads data into array */
int load (FILE *InFile, int *ary_nbr, int size)
{
	/* array sunscript, loop control, and # actual data loaded */
	int i; 
	
	/* loads data from file into array */
	i = 0;
	while((fscanf(InFile, "%i", &ary_nbr[i]) != EOF) && ( i < size))
	{
		i++; 
	}

	/* returns actual data loaded to elements */
	return i;
}

/* prints an array of data */
void printtab (FILE *OutFile, int *ary_nbr, int ele)
{
	/* array sunscript, loop control */
	int i;

	for (i = 0; i < ele; i++)
	{
		fprintf(OutFile, "%7d", ary_nbr[i]);
		printf("%7d", ary_nbr[i]);
		if(i%10==9)
		{
			fprintf(OutFile, "\n");
			printf("\n");
		}
	}
}

/* Copies an array into a new dynamic array */
int *copyarray(int *ary_nbr, int ele)
{
	int i = 0;

	/* allocate 1-dim dynamic array */
	int *dyn_ary; 
	dyn_ary = (int*) malloc(ele * sizeof(int));

	/* copy ary_nbr into dyn_ary*/
	for (i = 0; i < ele; i++)
	{
		dyn_ary[i] = ary_nbr[i];
	}
	return dyn_ary;
}

/* BubbleSorts an array */
void sortarray (int *dyn_ary, int ele, int *comparisons, int *swaps)
{
	/* loop controls */
	int i, j;
	
	/* temporary variable to hold value */
	int temp;

	/* perform bubble sort */
	for(i = 0; i < ele; i++)
	{
		for(j = 0; j < ele - 1; j++)
		{
			++*comparisons;
			if(dyn_ary[j] > dyn_ary[j+1])
			{
				++*swaps;
				temp = dyn_ary[j+1];
				dyn_ary[j+1] = dyn_ary[j];
				dyn_ary[j] = temp;
			}
		}
	}
}

/* Binary searches a sorted array */
int binarysearch(int *dyn_ary, int data_item, int ele, int *bcomparisons)
{
	/* point to beginning, middle, and end of the array */
	int low, high, mid;
	low = 0, high = ele - 1;

	while(low <= high) 
	{
		mid = (low + high)/2;
	
		// is the data_item in lower or upper half?
		if (data_item < dyn_ary[mid])
		{
			high = mid -1;
			++*bcomparisons;
		}
		else if(data_item > dyn_ary[mid])
		{
			low = mid +1;
			++*bcomparisons;
		}
		else
		{
			return mid;				
		}
	}
	return -1;
	free(dyn_ary);
}

/* Linear searches an un-sorted array */
int lsearch(int *ary_nbr, int data_item, int ele, int *lcomparisons)
{
	/* loop control */
	int i = 0;
	
	for (i=0; i<ele;i++)
	{
		++*lcomparisons;
		if(ary_nbr[i]==data_item)
		{
			/* location */
			return i;
		}
	}
	return -1;
}

and my header file where the typedef needs to be, which also includes my function prototypes

Code:

/* function prototypes */

//Name: load
//Returns: integer
//Parameters:	File *InFile, pointer - points to input data file
//				int *ary_nbr, pointer - points to an array of integers
//				int size, integer - maxsize for size of array
//In: FILE *InFile, int *ary_nbr, int size
//In/Out: int *ary_nbr
//Out: None
//Description:	loads data from InFile into ary_nbr at a max 'size'
//				and returns the actual loaded size of the array
int load (FILE *InFile, int *ary_nbr, int size);

//Name: printtab
//Returns: void
//Parameters:	File *OutFile, pointer - points to output data file
//				int *ary_nbr, pointer - points to an array of integers
//				int ele, integer - actual size of array
//In: int *ary_nbr, int ele
//In/Out: FILE *OutFile
//Out: None
//Description:	prints the actual contents of ary_nbr loaded, which
//				equals int ele. Prints to both output text file,
//				and to screen
void printtab (FILE *OutFile, int *ary_nbr, int ele);

//Name: copyarray
//Returns: int*
//Parameters:	int *ary_nbr, pointer - points to an array of integers
//				int ele, integer - actual size of array
//In: int *ary_nbr, int ele
//In/Out: None
//Out: dyn_ary
//Description:	copys an array of integers from ary_nbr into
//				a dynamic array named dyn_ary
int *copyarray(int *ary_nbr, int ele);

//Name: sortarray
//Returns: void
//Parameters:	int *dyn_ary, pointer to a dynamic array of integers
//				int ele, integer - actual size of array
//				int *comparisons, pointer - holds # of comps
//				int *swaps, pointer - holds # of swaps
//In: int *dyn_ary, int ele
//In/Out: None
//Out: int *comparisons, int *swaps
//Description:	Sorts the actual data loaded by a BubbleSort,
//				then returns via parameter the # of comparisons
//				and swaps
void sortarray (int *dyn_ary, int ele, int *comparisons, int *swaps);

//Name: binarysearch
//Returns: int
//Parameters:	int *dyn_ary, pointer to a sorted array of integers
//				int data_item, integer - data to search for
//				int ele, integer - actual size of array
//				int *bcomparisons, pointer - holds # of comps
//In: int *dyn_ary, int data_item, int ele
//In/Out: None
//Out: int *bcomparisons,
//Description:	Searches the sorted array for a number, and 
//				then returns via parameter the # of comparisons
//				and returns the location, or if not found returns -1
int binarysearch(int *dyn_ary, int data_item, int ele, int *bcomparisons);

//Name: lsearch
//Returns: int
//Parameters:	int *ary_nbr, an array of integers
//				int data_item, integer - data to search for
//				int ele, integer - actual size of array
//				int *lcomparisons, pointer - holds # of comps
//In: int *ary_nbr, int data_item, int ele
//In/Out: None
//Out: int *lcomparisons,
//Description:	Searches the un-sorted array for a number, and 
//				then returns via parameter the # of comparisons
//				and returns the location, or if not found returns -1
int lsearch(int *ary_nbr, int data_item, int ele, int *lcomparisons);

typedef struct PerformanceData
{
	//gather the performance data
	//comparisons & swaps
} PerformanceData;

So do i take the data once its passed back to main, and simple send it to the struct in my header file, then call for the information in main from the struct?

This is confusing, because you're comparing the very same item, to the very same value. Once to see if it's < and again to see if it's >.

A human would do it once and call it one comparison, but I'm almost sure the computer will do it once for each sign - so two comparisons per loop are needed - unless of course, the first comparison is found to be true, then you need to either "jump" over the next increment of *bcomparisons, or compensate by decrementing it, one time, inside the if statement.

Although there is an inferred comparison of ==, that isn't explicitly made, so no comparison is made in the else part.

Code:

               	++*bcomparisons;
		if (data_item < dyn_ary[mid])
		{
			high = mid -1;
		        continue;           //or --*bcomparisons;  
                }
                ++*bcomparisons;
		else if(data_item > dyn_ary[mid])
		{
			low = mid +1;
		}
		else   //no explicit comparisons made here
		{
			return mid;				
		}

Go ahead and put your struct info in (three int's ?), and then you can simple assign the values, before you reset anything.

I wouldn't have set it up this way, but it's here, and this is an exercise for learning.

Code:

typedef struct PerformanceData
{
	//enter your struct members:
   int bcomparisons;
   int lcomparisons;
   int swaps;
   //and any other performance variables you need   
} PerformanceData;

Make one instance of PerformanceData, and then when the program returns from binarySearch(), be sure to assign the bcomparisons value:

(PerformanceData instance name).bcomparisons = bcomparisons;

and do it similarly, with the other performance variables.

Originally Posted by Adak

Make one instance of PerformanceData, and then when the program returns from binarySearch(), be sure to assign the bcomparisons value:

(PerformanceData instance name).bcomparisons = bcomparisons;

and do it similarly, with the other performance variables.

When you say "instance name" what is that?

thank you all. everything is working perfectly!