Binary Search - Strange Output
I'm putting together a few little progs I made over the last couple of days to make an anagram finder, which I will hopefully be able to work into some kind of engine for word games.
Anyway the user enters a word and the prog cycles through each permutation of it. For each cycle it does a binary search on a dictionary to check for a match. Strangely it seems to work fine sometimes, but other times its completely off.
Heres the head/main section:
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 20
#define MAXIT 250000
struct dir
{
char word[MAXLEN];
};
typedef struct dir dir;
static FILE *OpenFile(char *file, char *mode);
void LoadDictionary(dir *ptr);
dir* BinarySearch(dir *ptr, char *match, int size);
int main()
{
struct dir *p;
p = (struct dir *) malloc(MAXIT * MAXLEN);
LoadDictionary(p);
char word[10];
int len, x;
int permutations = 1;
char temp;
int matches=0;
printf("Enter a word up to 8 characters in length: ");
fgets(word, 10, stdin); len=strlen(word)-1; word[len]='\0';
for(x=2; x<=len; x++)
permutations*=x;
for(x=0; x<permutations; x++)
{
temp = word[x%len];
word[x%len] = word[(x+1)%len];
word[(x+1)%len] = temp;
if(BinarySearch(p, word, MAXIT) != NULL)
{
printf("%s\n", word);
matches++;
}
}
printf("PERMUTATIONS: %i\tMATCHES: %i", permutations, matches);
while((temp=getchar()) != '\n');
}
And heres the search function:
Code:
dir* BinarySearch(dir *ptr, char *match, int size)
{
dir *lo=ptr;
dir *hi=ptr+MAXIT;
ptr+=(size >> 1); //Jump to middle of dictionary
int shift=(size >> 1);
int quit=0;
while(quit < 50)
{
if(shift > 1) //Halve the shift size if greater than 1
shift=shift >> 1;
else
quit++;
if(ptr < lo || ptr >= hi)
return NULL;
else if(strcmp(match, ptr->word) < 0)
ptr-=shift;
else if(strcmp(match, ptr->word) > 0)
ptr+=shift;
else
return ptr;
//Debug output
printf("SHIFT: %i\tA: %s\tB: %s\n", shift, match, ptr->word);
}
return NULL;
}
For example if I enter the word 'dog' it should come up with 2 matches.It finds the word dog after 17 iterations, but when it searches for 'god' it goes way off to words begining with H. Eventually its keeps switching between 'Handelian' and 'hander' until the loop is killed as if 'god' lies somewhere between the two. I dont get why this is happening :(
