Binary Search of Array

This is a discussion on Binary Search of Array within the C Programming forums, part of the General Programming Boards category; ok i have the entire code working. there is one last thing i need to do. i must use a ...

  1. #16
    Registered User
    Join Date
    Apr 2010
    Posts
    58
    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?

  2. #17
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Unfortunately you didn't get my point earlier.
    Code:
    		if (data_item < dyn_ary[mid])
    		{
    			high = mid -1;
    			++*bcomparisons;
    		}
    		else if(data_item > dyn_ary[mid])
    		{
    			low = mid +1;
    			++*bcomparisons;
    		}
    		else
    		{
    			return mid;				
    		}
    If we reach the else case then how many comparisons were done in the above, and what will *bcomparisons be?
    In short, you need to increment the count regardless of the outcode of the comparison. Each iteration will increment the count once in one of the cases and twice in two out of the three cases.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #18
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  4. #19
    Registered User
    Join Date
    Apr 2010
    Posts
    58
    Quote Originally Posted by Adak View Post

    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?

  5. #20
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    By "instance" they mean the actual variable, not just the structure definition, but an actual variable:
    Code:
    struct foo aninstanceofstructfoo;
    Just like x is an instance of an integer (though you don't usually word it that way):
    Code:
    int x;
    An 'instance' of a variable just means the actual variable, not its type/structure definition.


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #21
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Yes the most logical thing to do is to increment the count just prior to performing the comparison, but unfortunately this isn't as easy or clear. In C++ I would recommend to put the comparison and the increment inside a separate function (custom less-than operator).
    In this case though, you could simply increment bcomparisons:
    • by one inside the if
    • by two inside the else-if
    • by two inside the else
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #22
    Registered User
    Join Date
    Apr 2010
    Posts
    58
    thank you all. everything is working perfectly!

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linear search for structure (record) array
    By jereland in forum C Programming
    Replies: 3
    Last Post: 04-21-2004, 08:31 AM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  3. Binary Search in C help
    By kce9751 in forum C Programming
    Replies: 2
    Last Post: 06-17-2003, 09:17 AM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 10:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21