Thread: Binary Search of Array

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    58

    Binary Search of Array

    i have here a binary search. I am trying to get the value of the number of comparisons and swaps performed and having problems with it. All my code is in 3 different files (a requirement). I must pass the total # of comparisons and swaps via a parameter. and i must return the location of the data_item back to main...please help!!

    here is the code, ill highlight the necessary stuff

    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 comparisons = 0;
    int swaps = 0;
    int bcomparisons = 0;
    
    
    int main(int argc,char *argv[])
    {	
    	/* declare array */
    	int ary_nbr[maxsize];
    	int *dyn_ary;
    	int data_item = 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;
    	}
    
    	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);
    
    	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);
    
    	/* bubble sorts the array */
    	sortarray (dyn_ary, elements, &comparisons, &swaps);
    
    	printf("\tBubble sort Performance Data:\n");
    	printf("\t%i comps\n", comparisons );
    	printf("\t%i swaps\n\n", swaps );
    
    
    	/* prints actual sorted data */
    	printtab (OutFile, dyn_ary, elements);
    
    	printf("\nenter the data to search for:");
    	scanf("%d", &data_item);
    
    	binarysearch(dyn_ary, data_item, elements, &bcomparisons);
    
    	/* close files */
    	fclose(InFile);
    	fclose(OutFile);
    	}	
    
    	/* else file_error_flag */
    	return file_error_flag;
    }
    here is the header file for function prototypes
    Code:
    /* function prototypess*/
    
    int load (FILE *InFile, int *ary_nbr, int size);
    
    void printtab (FILE *OutFile, int *ary_nbr, int ele);
    
    int *copyarray(int *ary_nbr, int ele);
    
    int sortarray (int *dyn_ary, int ele, int *comparisons, int *swaps);
    
    int binarysearch(int *dyn_ary, int data_item, int ele, int *bcomparisons);
    and here is the file for the bodies of the functions (well for binarysearch)
    Code:
    // Recursive binary search
    int binarysearch(int *dyn_ary, int data_item, int ele)
    {
    	// point to beginning and end of the array
    	int low, high, mid;
    	low = 0, high = ele - 1;
    	int bcomparisons =0;
    
    	// binary search, there is an AND in the middle of while()!!!
    	while(low <= high)
    	{
    		mid = (low + high)/2;
    		printf("\n mid points to address %i", mid);
    		// 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; /* found */
                             // to test info
    			printf("\n %i found at location %d!", dyn_ary[mid], &dyn_ary[mid]);
    		}
    	}
    
               // to test info
    	printf("\n performed with %d comparisons", bcomparisons);
    
    	return -1;
    }

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Hey,

    If you have a variable declared before and outside main() or any other function,then that variable is a global variable.

    These are the global variables in your program:
    Code:
    int comparisons = 0;
    int swaps = 0;
    int bcomparisons = 0;
    You don't want to have any of these global variables as parameters into your functions (which you have done). So remove them from both the functions parameter list, and from the function prototype parameter.

    << THEY ARE GLOBAL, AND THEY ARE ALREADY AVAILABLE FOR EVERY FUNCTION! >>

    If you need to pass them as parameters, then leave them in your parameter lists, and move these declarations of variables, to main(), and pass them as AUTOMATIC (local) variables.


    I'll comment on your other points in a few minutes.
    Last edited by Adak; 05-02-2010 at 04:31 PM.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The variable bcomparisons can't be declared in binarysearch(). That would make it local to that function, and it would be destroyed as soon as the function ended.

    You need to decalre bcomparisons in main(), and then pass it as a parameter, to binarysearch - but not just the variable itself. You need to pass the ADDRESS (same as a pointer), to that variable, so that variable can be modified, and retain it's value after binarysearch(), has finished.



    Code:
    // Recursive binary search
    int binarysearch(int *dyn_ary, int data_item, int ele) <<==add int *bcomparisons
    {
    	// point to beginning and end of the array
    	int low, high, mid;
    	low = 0, high = ele - 1;
    	int bcomparisons =0;     <<==remove this line
    
    	// binary search, there is an AND in the middle of while()!!!
            //binary searches don't need an AND in the while() test, although you see it
            //sometimes -- poor form.
    	while(low <= high)
    	{
    		mid = (low + high)/2;
    		printf("\n mid points to address %i", mid); <<==not address, INDEX
    		// is the data_item in lower or upper half?
    		if (data_item < dyn_ary[mid])
    		{
    			high = mid -1;
    			*bcomparisons++;  <<== added the asterisk for you
    		}
    		else if(data_item > dyn_ary[mid])
    		{
    			low = mid +1;
    			*bcomparisons++;  <<same as above
    		}
    		else
    		{
    			return mid; /* found */ <<==return line goes AFTER your printf(), right below here.
                             // to test info
    			printf("\n %i found at location %d!", dyn_ary[mid], &dyn_ary[mid]);
                            
    return line here: ==>>
    		}
    	}
    
               // to test info
    	printf("\n performed with %d comparisons", bcomparisons);
    
    	return -1;
    }
    Now in main, you can also print out bcomparisons, whenever you want. You'll need to add the "address of" operator, to the calling line of code, so: &bcomparisons, in the parameter list, and not just bcomparisons, OK?

    If you did NOT need to pass bcomparisons as a parameter, then a local variable (as you had it), would be fine. But since you need to pass it, these changes are needed.
    Last edited by Adak; 05-02-2010 at 04:48 PM.

  4. #4
    Registered User
    Join Date
    Apr 2010
    Posts
    58
    ok here is the new code. are my increments in the right place to compute all the bcomparisons? im getting a very large number, and it should be around 100 or less than that i think. The location(mid) is working well. here is the updated code

    Code:
    int binarysearch(int *dyn_ary, int data_item, int ele, int *bcomparisons)
    {
    	// point to beginning and end of the array
    	int low, high, mid;
    	low = 0, high = ele - 1;
    
    
    	while(low <= high)
    	{
    		mid = (low + high)/2;
    		printf("\n mid points to index %i", mid);
    		// 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
    		{
    			
    	
    			printf("\nbinary search for %i found at location [%d] with %d comps!", data_item, mid, *bcomparisons);
    		printf("\n this is the mid %d", mid);
    		
    			return mid; /* found */
    				
    		}
    		
    	}
    	
    
    getchar();
    getchar();
    
    }

    here is the new code in main
    Code:
    int *bcomparisons = 0;
    
    binarysearch(dyn_ary, data_item, elements, &bcomparisons);
    and here is the function prototype:
    Code:
    int binarysearch(int *dyn_ary, int data_item, int ele, int *bcomparisons);
    and also, if i search for a number that isnt in the array, it needs to show up as a mid = -1. i tried putting that in the code but couldnt get it to work.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You have:

    return mid;

    Which is fine, if the target of the search was found.

    You ALSO need to have:

    return -1;

    To indicate that the search target wasn't found. That will be outside the while loop, like what you had in your previous post.

    When you say "couldn't get it to work", what was it that didn't work?

    Oh! I see the problem -- it's this:

    Code:
    binarysearch(dyn_ary, data_item, elements, &bcomparisons);
    you have to have a variable to "catch" the returned value from the binarysearch() function. Otherwise, it's just lost. (and NO, you don't need to have another variable named "mid" in main() and send the address of it to binarysearch(), etc.). You could do it that way, but it's very unusual (I've never seen it), and unnecessary.

    Just have a (signed) int variable to "catch" the return value of the search function:

    result = binarysearch(all your parameters in here);

    So result is the variable that you'll test to see if it's > -1. If it is, then your target was found. If not, then it wasn't found.
    Last edited by Adak; 05-02-2010 at 08:22 PM.

  6. #6
    Registered User
    Join Date
    Apr 2010
    Posts
    58
    o yes, you are correct! i have the locations returning to main fine, the only problem im having now is getting the comparisons to return correctly via parameters.

    prototypes
    Code:
    int sortarray (int *dyn_ary, int ele, int *comparisons, int *swaps);
    
    int binarysearch(int *dyn_ary, int data_item, int ele, int *bcomparisons);
    
    int lsearch(int *ary_nbr, int data_item, int ele, int *lcomparisons);
    main
    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 = 0;
    	/* 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;
    	}
    
    	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);
    
    	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);
    
    
    	/* bubble sorts the array */
    	sortarray (dyn_ary, elements, &comparisons, &swaps);
    
    		printf("\tBubble sort Performance Data:\n");
    	printf("\t%i comps\n", comparisons );
    	printf("\t%i swaps\n\n", swaps );
    
    	
    
    
    	/* prints actual sorted data */
    	printtab (OutFile, dyn_ary, elements);
    
    	printf("\nenter the data to search for:");
    	scanf("%d", &data_item);
    
    	
    	
    
    	b_location = binarysearch(dyn_ary, data_item, elements, &bcomparisons);
    
    	printf("\n\nthis is the bsearch location in main: %d\n", b_location);
    
    	l_location = lsearch(ary_nbr, data_item, elements, &lcomparisons);
    
    	printf("\n\nthis is the lsearch location in main: %d\n", l_location);
    
    
    	/* close files */
    	fclose(InFile);
    	fclose(OutFile);
    	}	
    
    	/* else file_error_flag */
    	return file_error_flag;
    }
    and the function bodies
    Code:
    int sortarray (int *dyn_ary, int ele, int *comparisons, int *swaps)
    {
    	int j;
    	int i;
    	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;
    			}
    		}
    	}
    	// to test values
    	printf("this is comparisons: %d", comparisons);
    	printf("this is swaps: %i", swaps);
    	
    }
    
    // Recursive binary search
    int binarysearch(int *dyn_ary, int data_item, int ele, int *bcomparisons)
    {
    	// point to beginning and end of the array
    	int low, high, mid;
    	low = 0, high = ele - 1;
    
    	while(low <= high) 
    	{
    		mid = (low + high)/2;
    		printf("\n mid points to index %i", mid);
    		// 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
    		{
    			printf("\nbinary search for %i found at location [%d] with %d comps!\n", data_item, mid, *bcomparisons);
    			return mid;				
    		}
    	}
    	return -1;
    getchar();
    getchar();
    free(dyn_ary);
    }
    
    int lsearch(int *ary_nbr, int data_item, int ele, int *lcomparisons)
    {
    int i = 0;
    
       for (i=0; i<ele;i++)
       {
          if(ary_nbr[i]==data_item)
          {
             *lcomparisons++;
    		 printf("\nlinear search for %i found at location [%d] with %d comps!\n", data_item, i, *lcomparisons);
             return i;
          }
       }
       printf("\nlinear search for %i found at location [%d] with %d comps!\n", data_item, i, *lcomparisons);
       return -1;
    
    
    }
    i had the swaps working for the sort array, but i had the values as global, and i cant do that, they need to be local and sent via parameters. i just cant seem to get these comparisons to work correctly!!!

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    you need an if statement before the printf saying where the binary location is - what if the target wasn't found at all?

    Do it like I posted in my last post.


    This is wrong:
    Code:
    	printf("this is comparisons: %d", comparisons);
    	printf("this is swaps: %i", swaps);
    comparisons in this function are just pointers - and have just addresses for values. You want to add the * and print the values they are pointing at, instead.

    binary search you use, is not recursive, it is iterative.

    This is the problem:

    Code:
    	/* 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;
    In main, comparisons (all of them), are just int's - regular plain integer variables.

    When you call a function, and it will change comparison variable, then it has to have the ADDRESS of comparison:
    Code:
    myFunction(&comparison);
    Now myFunction will receive this ADDRESS, AS A POINTER, NOT an integer, so you write:
    Code:
    int myFunction(int *comparison) {
      //all the code for myFunction in here:
      ++*comparison;
      comparison*--;                        
      //whatever
    }
    And you don't need to return comparison, because main will already have the right value in the int variable of comparison.
    Last edited by Adak; 05-02-2010 at 09:16 PM.

  8. #8
    Registered User
    Join Date
    Apr 2010
    Posts
    58
    whenever i apply the * to comparisons in the function...the program runs but it always gets an "unexpected error".

    and do all the comparison variables in the funcitons need a * to?

    because something is still amiss...

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Yes they do, and I didn't show that in my little example above. I've edited it to correct that.

    Inside the called function like binarysearch(int *comparison), comparison without a * is just an address, and if you increment that, you'll get that "unexpected error" since the variable is not pointing where it should, anymore.

  10. #10
    Registered User
    Join Date
    Apr 2010
    Posts
    58
    now its working! do you think there is a better way to get the increments for the linear search? i dont believe it is producing the correct result...and how could i go about continually prompting the user for a number to search for until the user enters a negative number? a for or if statement?

    EDIT* i have the increments working well for the linear search, i had the variable in the wrong spot
    Last edited by pantherman34; 05-02-2010 at 10:29 PM.

  11. #11
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by pantherman34 View Post
    now its working! do you think there is a better way to get the increments for the linear search? i dont believe it is producing the correct result...and how could i go about continually prompting the user for a number to search for until the user enters a negative number? a for or if statement?
    Code:
    do{
    
     /* read nr */
    
    }while(nr >= 0);
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  12. #12
    Registered User
    Join Date
    Apr 2010
    Posts
    58
    ok. the do statement works well. its just one thing - whenever the search runs again...i need the comparisons to set back to zero. the way it is now, the comparisons add together.

    Code:
    do
    	{
    	/* prompts user for data to search for */
    	printf("\n\n\tEnter the data to search for: ");
    	scanf("%d", &data_item);
    
    	/* searches sorted array, and 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 %i found at location [%d] with %d comps!\n", data_item, l_location, lcomparisons);
    	printf("\tBinary Search for %i found at location [%d] with %d comps!", data_item, b_location, bcomparisons);
    	}
    	while (data_item >= 0);
    how could i set the comparisons back to zero? i might have an idea now that ive written this. feel free to share your input

  13. #13
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by pantherman34 View Post
    ok. the do statement works well. its just one thing - whenever the search runs again...i need the comparisons to set back to zero. the way it is now, the comparisons add together.

    Code:
    do
    	{
    	/* prompts user for data to search for */
    	printf("\n\n\tEnter the data to search for: ");
    	scanf("%d", &data_item);
    
    	/* searches sorted array, and 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 %i found at location [%d] with %d comps!\n", data_item, l_location, lcomparisons);
    	printf("\tBinary Search for %i found at location [%d] with %d comps!", data_item, b_location, bcomparisons);
    	}
    	while (data_item >= 0);
    how could i set the comparisons back to zero? i might have an idea now that ive written this. feel free to share your input
    first of all you should have another if after the scanf to check that the first value you read is not invalid

    scanf("%d", &data_item);

    if(data_item < 0) break;
    else /* reset bcomparisons */
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You incrementing of bcomparisons inside binarysearch is not right. As an illustration, consider what the value of bcomparisons is after executing the folowing code:
    Code:
    int bcomparisons = 0;
    int a = 7, b = 3;
    if (a < b)
    {
        bcomparisons++;
    }
    Hmm, well it compared 7 to 3, but bcomparisons is 0 instead of 1! Can you see what the problem is? Hint: You got it correct in your bubble sort.
    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"

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Good "i" Malcolm.

    You know where to move the comparison increment, right above (instead of inside), the if() block of code making the comparison.

    I would set the comparison variable to 0, right inside the search function, top of the function:
    Code:
    *comparison = 0;  //not int comparison = 0, that's for local variables, you have a pointer remember
    Last edited by Adak; 05-03-2010 at 07:39 AM.

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, 07: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, 08:17 AM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM