okay, why is this not working??????

[rogenie]

here is my code. I don't know why it always returns the value that i do not ask for.?? This code display the name I typed in if it is inside the array.

//this will sort strings using selection sort
#include <iostream>
using namespace std;

const int NUM_NAMES = 20, SIZE = 17;

//function prototype
void selectionSort( char array[][SIZE], int size );
int binarySearch( char array[][SIZE], int numelems, char value[SIZE] );


int main()
{
    char names[NUM_NAMES][SIZE] = {
            "Collins, Bill", "Smith, Bart", "Allen, Jim",
            "Griffin, Jim", "Stamey, Marty", "Rose, Geri",
            "Taylor, Terri", "Johnson, Jill",
            "Allison, Jeff", "Looney, Joe", "Wolfe, Bill",
            "James, Jean", "Weaver, Jim", "Pore, Bob",
            "Rutherford, Greg", "Javens, Renee", 
            "Harrison, Rose", "Setzer, Cathy",
            "Pike, Gordon", "Holland, Beth",  };
 
    int result;
    char nameString[SIZE];
 
    selectionSort( names, NUM_NAMES );
 
    cout << "Enter name: ";
    cin.getline( nameString, SIZE );
 
    result = binarySearch( names, NUM_NAMES, nameString );
 
    if( result == -1 )
        cout << nameString << " is not in the list.\n";
    else
        cout << names[result] << " found.\n";
 
    return 0;
}
/*displayStrings function
void displayStrings( char array[][SIZE], int size )
{
    for( int index = 0; index < size; index++ )
        cout << array[index] << endl;
}*/

//selectionSort function
void selectionSort( char array[][SIZE], int size )
{ 
    int startScan, minIndex;
    char minValue[SIZE];
 
    for( startScan = 0; startScan < (size - 1); startScan++ ) 
   {
 
        minIndex = startScan;
        strcpy( minValue, array[startScan] );
 
        for( int index = startScan + 1; index < size; index++ )
        {
            if( strcmp( array[index], minValue ) < 0 ) {
                strcpy( minValue, array[index] );
                minIndex = index;
             }
        }
 
        strcpy( array[minIndex], array[startScan] );
        strcpy( array[startScan], minValue );
 
    }
	 
}

//The binarySearch function
int binarySearch( char array[][SIZE], int numElems, char value[SIZE] )
{
	int first = 0,
		last = numElems - 1,
		middle,
		position = -1;
	bool found = false;
	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (array[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (array[middle] > value)
			last = middle - 1;
		else
			first = middle + 1;
	}
	return position;
}

[WaltP]

here is my code. I don't know why it always returns the value that i do not ask for.?? This code display the name I typed in if it is inside the array.

Probably because you returned the value you didn't want.

Because you didn't explain
1) what you wanted
2) what the program did
3) where the error is
there's not much to tell you.

I guess you didn't understand the information listed in the post at the top of the forum titled "Read Me: Read This Before Posting", eh?

[rogenie]

Probably because you returned the value you didn't want.

Because you didn't explain
1) what you wanted
2) what the program did
3) where the error is
there's not much to tell you.

I guess you didn't understand the information listed in the post at the top of the forum titled "Read Me: Read This Before Posting", eh?

This is suppose to ask the user to type in the name and display the name if it is inside the array. Otherwise a message displays "The name is invalid". I am using binary search (binarySearch function) to search through the array and sorting the array first using selection sort (selectionSort function).

[WaltP]

One out of three questions answered. Want to go for two out of three?

You didn't read that link, did you?

[vmanes]

Look at how you're doing the comparisons in binary search function. What's really being compared?

[rogenie]

Look at how you're doing the comparisons in binary search function. What's really being compared?

binarySearch function is suppose to start searching from the middle of the array then go up. if the value the user entered is not there, then start searching again from the middle of the array going down. To my understanding what is really being compared here is the element from the middle of the array to the last element? the same thing as with the binary search going from the middle element of the array going down. Yea? I don't understand well.. We just started with functions and this is still very new and fresh to me

[vmanes]

I wasn't referring to what you were comparing, your search function looks to be properly structured.

Look at HOW you are comparing in it.

Val

[rogenie]

I can't be possibly comparing it wrong because this is what the book said??

[rogenie]

ohhh, Hmm I am comparing strings.. why am I using int?? I should use strcpy?? Let me try

[vmanes]

ohhh, Hmm I am comparing strings.. why am I using int?? I should use strcpy?? Let me try

Huh?

Look at this bit of your code:

if (array[middle] == value)
		{
			found = true;
			position = middle;
		}
		else if (array[middle] > value)
			last = middle - 1;

array[middle] and value are (C-style) strings. You cannot compare them with == or >.

Well, you can, but you'd actually be comparing the memory addresses at which they start. You need to use on of the strcmp( ) functions, as you correctly do in the sorting function.

Val

[rogenie]

//The binarySearch function
int binarySearch( char array[][SIZE], int numElems, char value[SIZE] )
{
    int first = 0,
        last = numElems - 1,
        middle,
        position = -1;
    bool found = false;
    while (!found && first <= last)
    {
        middle = (first + last) / 2;
        if (strcmp(array[middle], value) == 0)
        {
            found = true;
            position = middle;
        }
        else if (strcmp(array[middle], value) > 0)
            last = middle - 1;
        else
            first = middle + 1;
    }
    return position;
}

thats what I end up with and still digesting little by little. I just dont get this comparing C-strings stuff.

[vmanes]

Your binary search now appears correct.

"thats what I end up with and still digesting little by little. I just dont get this comparing C-strings stuff."

Consider the following:

// NOTE:  incorrect code follows!
int arr1[5] = { 1, 3, 5, 7, 9 };
int arr2[5] = { 9, 7, 5, 3, 1 };

if ( arr1 < arr2 )
   cout << "arr1 is smaller";
else
   cout << "arr2 is smaller";

What does it mean to say that one array is smaller (or greater) than the other? It doesn't really make any sense, as there are many ways you could define greater and lesser.

When you use just the name of the array (as above), without any index, you are referring to the address of the first member, the same as saying &arr[0] . Does is do any good to compare their addresses?

A C-style string is, after all, just an array of characters, and so comparing one array to another does us no good. Unlike the numeric arrays above, we do have clear concept of what it means for one array to be considered "less than" or "greater than" another (though I prefer to say "comes before" or "comes after" in sorting order.)

At its simplest (and this does not take into account unicode or varying usages in other locales), a string compare function can be written as:

int str_compare( const char *str1, const char *str2)
{
  int diff;
   int i;

   i=0;
   // test to see if either string still has valid characters.
	// if both strings end at same position, they are equivalent
   while( str1[i] != '\0' || str2[i] != '\0')
   {
      // subtract the integer values of the two characters
      diff = (int)str1[i] - (int)str2[i];

      // if the difference is not zero we now know the order
      // of the strings.
      if(diff != 0)
         return diff;
      
      // move to the next character in both arrays
      i++;
   }

   // both strings ran out of characters, they are equivalent
   return 0;
}

So, the function returns a value that will point to the string argument that comes earlier in the sorting (ASCII) order. Some implantations will return exactly -1, 0 o +1, others will return the negative or positive value that resulted from the subtraction that had the difference, or 0. So it's best to always write your use of strcmp( ) functions in terms of >0 or <0, rather than testing for exaclty -1 or +1 as return values.

Has this muddied the waters enough for you?

Val

[rogenie]

Hi thanks for all the input. I dropped out of the class and decided to go the the classroom instead on spring. I will make sure to pest on my teacher anytime I don't understand anything. This is just too hard learning on my own and hoping to get some answers from various forums. I could put a homewrk together but I am not really understanding it fully:=)

[rogenie]

I got the problem solved by the way.. I read your last post over and over again. below is my final code...

const int NUM_NAMES = 20, SIZE = 17;

//function prototype
void selectionSort( char array[][SIZE], int size );
int binarySearch( char array[][SIZE], int numelems, char value[SIZE] );


int main()
{
    char names[NUM_NAMES][SIZE] = {
            "Collins, Bill", "Smith, Bart", "Allen, Jim",
            "Griffin, Jim", "Stamey, Marty", "Rose, Geri",
            "Taylor, Terri", "Johnson, Jill",
            "Allison, Jeff", "Looney, Joe", "Wolfe, Bill",
            "James, Jean", "Weaver, Jim", "Pore, Bob",
            "Rutherford, Greg", "Javens, Renee", 
            "Harrison, Rose", "Setzer, Cathy",
            "Pike, Gordon", "Holland, Beth",  };
 
    int result;
    char nameString[SIZE];
 
    selectionSort( names, NUM_NAMES );
 
    cout << "Enter name: ";
    cin.getline( nameString, SIZE );
 
    result = binarySearch( names, NUM_NAMES, nameString );
 
    if( result == -1 )
        cout << nameString << " is not in the list.\n";
    else
        cout << names[result] << " found.\n";
 
    return 0;
}
//displayStrings function
void displayStrings( char array[][SIZE], int size )
{
    for( int index = 0; index < size; index++ )
        cout << array[index] << endl;
}

//selectionSort function
void selectionSort( char array[][SIZE], int size )
{ 
    int startScan, minIndex;
    char minValue[SIZE];
 
    for( startScan = 0; startScan < (size - 1); startScan++ ) 
   {
 
        minIndex = startScan;
        strcpy( minValue, array[startScan] );
 
        for( int index = startScan + 1; index < size; index++ )
        {
            if( strcmp( array[index], minValue ) < 0 ) {
                strcpy( minValue, array[index] );
                minIndex = index;
             }
        }
 
        strcpy( array[minIndex], array[startScan] );
        strcpy( array[startScan], minValue );
 
    }
	 
}

//The binarySearch function
int binarySearch( char array[][SIZE], int numElems, char value[SIZE] )
{
	int first = 0,
		last = numElems - 1,
		middle,
		position = -1;
	bool found = false;
	while (!found && first <= last)
	{
		middle = (first + last) / 2;
		if (strcmp(array[middle], value) == 0)
		{
			found = true;
			position = middle;
		}
		else if (strcmp(array[middle], value) > 0)
			last = middle - 1;
		else
			first = middle + 1;
	}
	return position;
}

[rogenie]

in a post quick reply there is not preview button?? Also there is no CODE tag in there. Only quote

[WaltP]

So type the CODE tags in or hit "GO ADVANCED". Don't just make a rotten post because the Quick Reply box isn't perfect for you...