Binary Search

Hey I am doing a binary search and then passing in a stucture called state. It seaches for the abbreviation to make sure it is in the table and everytime I run it, although it is valid I get that it's not a valid state. I'm not sure what I'm doing wrong here.
//structure for state and state type
struct state
{
	char name[15];
	char abbr[3];
};

struct stateType
{
	state lists[51];
};
//this is in main
get_str("Please enter a state: ", stateABB);
checkState(point_STname, stateABB);

//function to check the state abbr
int checkState (struct stateType* STname, char stateABB[])
{
	static char f_time;
	f_time = 'Y';
	if (f_time == 'Y')
	{
		char buffer[50];
		FILE *fp;
		fp = fopen("STATES.DAT", "r");
		if (fp == NULL)
		{
			printf ("Error opening file! ");
		}
		 
		int counter = 0;
	
		while(!(feof(fp)))
		{
			
			fgets(STname->lists[counter].name, 20, fp);
			STname->lists[counter].name[strlen(STname->lists[counter].name)-1] = '\0';
			fgets(STname->lists[counter].abbr, 20, fp);
			STname->lists[counter].abbr[strlen(STname->lists[counter].abbr)-1] = '\0'; 
			
			
			++counter;
		}

		f_time == 'N';
	}

	int first=0,last = 50, middle, position=-1;
	bool found=false;
	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (STname->lists[middle].abbr == stateABB)
		{
			found = true;
			position = middle;
		}
		else if (STname->lists[middle].abbr > stateABB)
		{
			last = middle - 1;
		}
		else
		{	
			first = middle + 1;
		}
	}
	
	if (position == -1)
	{
		printf ("Not a valid state abbreviation");
		get_str("Please enter a state: ", stateABB);
	}
	else
	{
		printf ("This is a valid state");
		//store in structure
	}
	return position;
}

Open in new window

reesee324Asked:
Who is Participating?
 
ozoCommented:
           middle = (first + last) / 2;
            Compare = strcmp (STname->lists[middle].abbr, stateABB);
                  if (Compare == 0)
                  {
                        found = true;
                        position = middle;
                  }
                  else if (Compare > 0)
                  {
                        last = middle - 1;
                  }
                  else
                  {      
                        first = middle + 1;
                        
                  }

0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi reesee,

That's not a "classic" binary search, but it looks like it should work just fine.

One requirement of a binary search is that the data is sorted correctly.  In this case you probably want alphabetical order.  And case is important.

It looks like you're comparing character arrays (C code) not strings (ANSI strings in C++ code).  For this use strcmp, not ==

  if (strcmp (STname->lists[middle].abbr, stateABB) == 0)

And you really want to test this a couple of times per pass, so..


  Compare = strcmp (STname->lists[middle].abbr, stateABB);
  if (Compare == 0)

etc....


Good Luck,
Kent
0
 
reesee324Author Commented:
When I put it in the function it says that the "argument of type bool is incompatible with paramater of type "const *char"
0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
ozoCommented:
An easy way to get that error is to put the wrong thing in the function.
How did you incorporate the suggestion into your code?
0
 
reesee324Author Commented:
This is what I have now but I don't think I have it right because now I get a break that says the variable 'middle' is being used without being initialized. I've been looking at this for too long!
int checkState (struct stateType* STname, char stateABB[])
{
	static char f_time;
	f_time = 'Y';
	if (f_time == 'Y')
	{
		char buffer[50];
		FILE *fp;
		fp = fopen("STATES.DAT", "r");
		if (fp == NULL)
		{
			printf ("Error opening file! ");
		}
		 
		int counter = 0;
	
		while(!(feof(fp)))
		{
			
			fgets(STname->lists[counter].name, 20, fp);
			STname->lists[counter].name[strlen(STname->lists[counter].name)-1] = '\0';
			fgets(STname->lists[counter].abbr, 20, fp);
			STname->lists[counter].abbr[strlen(STname->lists[counter].abbr)-1] = '\0'; 
						
			++counter;
		}

		f_time == 'N';
	}
	
	
	int first=0,last = 50, middle, position=-1;
	bool found=false;
	
	while (!found && first <= last)
	{
		int Compare;
		Compare = strcmp (STname->lists[middle].abbr, stateABB);
		middle = (first + last) / 2;
		if (Compare == 0)
		{
			if (STname->lists[middle].abbr > stateABB)
			{
				found = true;
				position = middle;
			}
			else if (STname->lists[middle].abbr > stateABB)
			{
				last = middle - 1;
			}
			else
			{	
				first = middle + 1;
				
			}
		}
	}
	if (position == -1)
	{
		printf ("Not a valid state abbreviation");
		get_str("Please enter a state: ", stateABB);
	}
	else
	{
		printf ("This is a valid state");
		//store in structure
	}
	return position;
}

Open in new window

0
 
reesee324Author Commented:
Sweet! Thank you so much for your help!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.