Thread: binary search function on string array

This program is a dictionary program. I am loading a list of words from a file, sorting as I insert. The program also has a search function that uses the same code. Some of the words inserted into the array are in the wrong order. Am I missing something with this function?

This program is being compiled on Debian Linux with the 4.1.2 gcc compiler.

Thanks in advance.

Code:

int indexOfWord( char ** dictionary, int count, char *word )
{
   int lowerBound     = 0; 
   int upperBound     = count - 1;
   int midPoint       = 0;
   int strCompResults = 0;

   while (lowerBound < upperBound ) {
     midPoint       = (upperBound + lowerBound)/2;
     strCompResults = strcmp(word,dictionary[midPoint]);

          if ( strCompResults ==  0) return midPoint;
     else if ( strCompResults  >  0) lowerBound     = midPoint + 1;
     else                            upperBound     = midPoint - 1;
 }

  return midPoint * -1;
}

I don't know whether it is shear coincidence. I asked almost for a similar routine how it can be improvised. My logic is also more or less than same. Anyways coming to your point please find my observation. Also please note i have not tested it and i worked it out by scribbling on paper.

Code:

Assuming the element you want to search is at Position 9 and the number of elements is 18

Elements -> 18
Lower Bound -> 0
Upper Bound -> (18 - 1) 17
Mid Point -> (17 + 0) -> 8

Search element is greater than position 8

Lower Bound -> 9
Upper Bound -> 17
Mid Point ->   13

Search element is less than position 13

Lower Bound -> 9
Upper Bound -> 12
Mid Point   -> 10

Search element is less than position 10

Lower Bound -> 9
Upper Bound -> 9

Loop will exit (because of the while loop (lowerbound < upperbound)

So replace the while loop with this condition and hopefully it should work. Please note it is not tested

Code:

(while lowerBound <= upperBound  )

Hope it helps

Regards

Raj

Thanks to all for the help. I took another look at the insertWord, the result must be off by 2 or more on occasion. So adding changing if to while causes the program to make the proper adjustment. and I also had to look at the previous item in the array to see if I was inserting to far back in the list. Once again using a while list to make the adjustment if the difference is more than one. This code should work for my needs. Thanks again.

Code:

void insertWord( char ***dictionary, int *count, int *capacity, char *word )
{
   int wordLocation      = 0;
   int i = 0;

  if (*count == *capacity) /* need to double my array's capacity! */
         resizeDictionary(dictionary, capacity);

/* find the location of where the word should reside. For the first few words the wordLocation
 * method does not seem to work, so I plan on doing the first few words manually. */
   wordLocation = indexOfWord( *dictionary, *count, word );

   if (wordLocation < 1 || *count == 0)
   {
/*    A negative word location means that the word is not in the array */
      wordLocation *= -1;
/*    check to see if I am off by one, if so adjust the index. */
      if (*count > 0 )
      {
         while (wordLocation < *count && strcmp(word, (*dictionary)[wordLocation])   > 0) ++wordLocation;

         while (wordLocation > 0      && strcmp(word, (*dictionary)[wordLocation-1]) < 0) --wordLocation; 
      }

/*      printDictionary( *dictionary, *count, stdout );
      printf("%d \n",wordLocation );
*/
/*    The for loop is written to start at the end and move every string out one position.
 *    thus freeing up a spot the the please returned by indexOfWordReturn */
      for (i=(*count)-1 ; i>=wordLocation ; --i )
      {
        (*dictionary)[i+1] = (*dictionary)[i];
      }
/*    copy ptr to the correct location in the dictionary array */
      ++*count;
      (*dictionary)[wordLocation] = word;
   }
}