Binary word search

[ej2k]

I'm trying to do a search for a word in a word list.

The word list looks like:
a
an
any
bag
cat
dog
etc.


I would like to do a binary search for the word. I have the word list in an array of pointers. Any idea how to go about this?

 

[Pappy1942]

Hi,
If the list is an array, I assume you know how many words there are.
Compare 'strcmp()' the search word(SW) with the middle list word.
If the SW is greater then compare the SW with the list word half way between the
middle list word and the last list word. If SW is less than middle list word compare the SW with the list word between the first list word and the middle list word.

given SW = 'any' and the list you posted
compare any to bag
any is less than bag
compare any to an
any is greater than an
compare any to any
any is the same as any DONE

Hope this helps.
Pappy

 

[ej2k]

Thanks loads - that really helped!!! I was getting really worried that it couldn't be done easily.

Thanks again.

 

[rbobbitt]

It can be done even easier than that!

There is a standard function called bsearch() which performs binary searches the way Pappy described.


Russ
bobbitts@hotmail.com

http://home.earthlink.net/~bobbitts