Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Re^3: Check word presence WITHOUT hashes or grep

by stiller (Friar)
on Apr 30, 2008 at 07:07 UTC ( #683639=note: print w/replies, xml ) Need Help??

in reply to Re^2: Check word presence WITHOUT hashes or grep
in thread Check word presence WITHOUT hashes or grep

Binary search, and algorithms in general, is a field you must try to get a grasp on no matter what programming languages you work with. Often in a high level programming language you don't need to implement them yourself, but understanding these issues will have profound impact on how well you can learn and exploit a particular programming language. The more algorithms and datastructures you are familiar with, the easier it will be to see good simple solutions to what seems a hard task without such knowledge.

Binary search is the process where you halve the remaining search space for each test. So, lets say you have your dictionary of say 100.000 words in a SORTED array. Now you want to test if the word Trzagrat is in there somewhere. First you look on the position in the middle of your dictionary array. Either you find the word there, or if not, you will know which half of the dictionary must hold the word if it's there at all, because the dictionary is sorted, and the word you're looking up either sorts before or after the word you found at this position. So you contiune...

A better explanation on Wikipedia, binary search

  • Comment on Re^3: Check word presence WITHOUT hashes or grep

Replies are listed 'Best First'.
Re^4: Check word presence WITHOUT hashes or grep
by gojippo (Novice) on Apr 30, 2008 at 07:16 UTC
    Thank you for your explanation, stiller. I updated just when you posted your message. I managed to understand the logic of binary search, but I don't understand the how-to-do-it part. Do you have an easy-to-understand example ? It would really help.
      Try to write the pseudo code, explaining the point of each step, first. Then make an attempt at an implementation. I'll comment on that if you get stuck and post it here.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://683639]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (7)
As of 2018-05-24 14:52 GMT
Find Nodes?
    Voting Booth?