- - - - What's wrong with my code

[DaniDak]

Hi,
I have problems with my binary search function;
I have a 2D char array- with multi-word strings in it.
I have 5 strings, each string is of length 30.
e.g.
arr[0][30]={String number one};
arr[1][30]={Number two};
:
:
---
char *s =is the string to search for
char a[][MAX] = is the 2d array
int size = length of the string (30 or MAX)
---
If I try to search for word [two] I get not found,
but if I search for Number two, I get found at index 1.

I need to find the word inside the array and report the location of the word.
Like found in index 1 at position 8.

I really need help.
thank you

int binery_search(char *s, char a[][MAX], int size)
{
int low = 0;
int high = size;
int mid, value;

while (low <= high)
{
mid = (high + low)/2;
value = strcmp(s, a[mid]); //*************
if (value == 0)
return mid; // found
else if (value < 0)
high = mid-1;
else
low = mid+1;
}
return -1; // not found
}

thank you again.

 

[BoulderBum]

Two things to check out:

1. Are you trying to store double scripted arrays of chars, or double scripted arrays of strings. I get the impression that you think you may have seperate strings for each element, but your definitions are for single chars. i.e.
char[0][0] == 'c'
char[0][1] == 'a'
char[0][2] == 't'
char[0][3] == '\0'
If you do in fact want char arrays, you only need to return the row index, which is what you seem to be doing (e.g. return 0 for &quot;cat&quot.

2. The integer variable &quot;size&quot; shouldn't necessarily be the length of the string, rather it should be the number of words in the array - 1 for zero indexing. e.g.

char[0]* == cat ...1st word
char[1]* == dog ...2nd word
char[2]* == rat ...3rd word

size would need to be the number of words - 1, 2 in this case, in order to perform the binary search correctly.

 

[DaniDak]

My mistake I'm sending the number of words, not the size of string, but still it doesn't work.

if anyone has any other ideas what could be wrong
I would really appreciate.

 

[BoulderBum]

Well, if you are searching for the second word, it <i>should<i> be found at index 1 (because of zero indexing).

What is returned when you make this call?:

binery_search( a[3], a, #ofWordsMinusOne )

 

[DaniDak]

Still I get the same thing,
word not found.

any other ideas, because I couldn't find anything in my books(3 of them) or the net, that is even close to what I need to do.

 

[JOLESEN]

The strcmp() function will only compare null terminated strings - whole strings.
To find 'substrings' you could use the strstr() function.
/JOlesen

 

[DaniDak]

I tried using the strstr() function (see bellow) but the value returned is just an address not the position where the word was found. But I'm not sure if did it right.

int binary_search(char* s, char a[][MAX], int size)
{
int low = 0;
int high = size;
int mid, value;
char* test;

while (low <= high)
{
test = strstr(a, s);
value = (test - a) + 1;

if (value < 0)
high = mid-1;
else if (value > 0)
low = mid+1;
else
return value; // found
}
}

 

[DaniDak]

something strange happened to my code before, when I posted it.

int binary_search(char* s, char a[][MAX], int size)
{
int low = 0;
int high = size;
int mid, value;
char* test;

while (low <= high)
{
test = strstr(a[mid], s); //compare
value = (test - a[mid]) + 1;

if (value < 0)
high = mid-1;
else if (value > 0)
low = mid+1;
else
return value; // found
}
}

 

[JOLESEN]

The string search looks ok.

You have some problems with your code :
1) You use mid without initializing it .. very unsafe.
2) Since you are searching for complete strings as well as substrings, why not simply search from start to end ?
I don't think it will work with your algorithm.
/JOlesen

 

[DaniDak]

My mistake I forgot to include the mid when I posted the code.
int mid = (low+high) /2;

I know it's not working, but I'm out of ideas.
Any suggestion.

 

[JOLESEN]

Unless you decide to only search for complete strings (single- as well as multi-words), my suggestion would be to search from start to end.

I don't know what you will use the code for, but you could also build an index for every word in the array.

/JOlesen

 

[BoulderBum]

I have a working version of this algorithm at home. I'll post it when I get off of work.

 

[DaniDak]

thank you very much
BoulderBum

 

[BoulderBum]

Actually I guess it was a recursive search of an integer array, so this may just confuse the matter more, but I'll see if I can do something else...

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <iomanip>

using std::setw;

int binarySearch( const int [], const int, int, int,
const int );
void printHeader( const int );
void printRow( const int [], const int, const int,
const int, const int );

int main()
{
const int arraySize = 15;
int a[ arraySize ], key, result;

for ( int i = 0; i < arraySize; i++ )
a[ i ] = 2 * i; // place some data in array

cout << &quot;Enter a number between 0 and 28: &quot;;
cin >> key;

printHeader( arraySize );
result = binarySearch( a, key, 0, arraySize - 1,
arraySize );

if ( result != -1 )
cout << '\n' << key << &quot; found in array element &quot;
<< result << endl;
else
cout << '\n' << key << &quot; not found&quot; << endl;

return 0;
}

// Binary search
int binarySearch( const int b[], const int searchKey,
int low, int high, const int size )
{
int middle;

middle = ( low + high ) / 2;
printRow( b, low, middle, high, size );

if ( searchKey == b[ middle ] ) // match
return middle;
else if ( low == high )
return -1; // searchKey not found
else if ( searchKey < b[ middle ] )
high = middle - 1; // search low end of array
else
low = middle + 1; // search high end of array

return binarySearch( b, searchKey, low, high, size );
}

// Print a header for the output
void printHeader( const int size )
{
int i;

cout << &quot;\nSubscripts:\n&quot;;

for ( i = 0; i < size; i++ )
cout << setw( 3 ) << i << ' ';

cout << '\n';

for ( i = 1; i <= 4 * size; i++ )
cout << '-';

cout << endl;
}

// Print one row of output showing the current
// part of the array being processed.
void printRow( const int b[], const int low, const int mid,
const int high, const int size )
{
for ( int i = 0; i < size; i++ )
if ( i < low || i > high )
cout << &quot; &quot;;
else if ( i == mid ) // mark middle value
cout << setw( 3 ) << b[ i ] << '*';
else
cout << setw( 3 ) << b[ i ] << ' ';

cout << endl;
}

 

[BoulderBum]

Check it. You're algorithm works. I don't know what's up, but I did realize that all of the elements in the character array need to be in alphabetical order for strcmp to work properly. Maybe that's where you're going wrong.

#include<iostream>
using std::endl;
using std::cout;

const int elements = 10,
length = 4;

int binarySearch(char *, char[][length], int);
void printArrayPart( const int, const int, char[][length]);

int main()
{
char s[elements][length] = {{ 'b', 'a', 't', '\0' },
{ 'c', 'a', 't', '\0' },
{ 'd', 'a', 'd', '\0' },
{ 'd', 'o', 'g', '\0' },
{ 'h', 'o', 'g', '\0' },
{ 'p', 'a', 't', '\0' },
{ 'p', 'u', 't', '\0' },
{ 's', 'e', 'w', '\0' },
{ 't', 'o', 'o', '\0' },
{ 'w', 'a', 'g', '\0' },};

char *searchFor = &quot;dad&quot;;

cout << &quot;******Original array******\n&quot;;
printArrayPart( 0, elements - 1, s );
cout << '\n';

if ( binarySearch( searchFor, s, elements - 1) == -1 )
cout << &quot;\nElement not found.&quot; << endl;

return 0;
}


int binarySearch(char *s, char a[][length], int size)
{
int low = 0;
int high = size;
int mid, value;

while (low <= high)
{
mid = (high + low)/2;
cout << &quot;\n****searching these elements****\n&quot;;
printArrayPart( low, high, a );

value = strcmp(s, a[mid]); //*************
if (value == 0)
{
cout << &quot;\n*****element found*****\n&quot;
<< '[' << mid << &quot;]\n&quot;
<< s << endl;
return mid; // found
}
else if (value < 0)
high = mid-1;
else
low = mid+1;
}
return -1; // not found
}



//prints part of an array according to given low and
//high subscripts
void printArrayPart( const int lowSub, const int highSub
,char array[][length])
{
//header
for ( int i = lowSub; i <= highSub; i++ )
cout << '[' << i << &quot;] &quot;;
cout << '\n';

//array elements
for ( int j = lowSub; j <= highSub; j++ )
cout << array[j] << ' ';

cout << endl;
}

 

[BoulderBum]

PS If you change the length variable, the printout of the subscripts will be messed up (it was a rush job), but I'm sure you'll forgive me.