Hey, and how about that...another use for binary search. I'm stuck in a Wikipedia rabbit hole about distributed hashing, and just ran into an in interesting use of a binary search. Imagine that you're trying to distribute storage or work amongst a bunch of things. For simplicity, imagine that you want to store records with names starting with "A" on one machine, "B" on another, and so on. If you have a list of addresses and a list of the starting strings, you can do a binary looking and get the right machine address.
A Machine 1 B Machine 2 ... and so on. So imagine 26 machines as a bucket for records, divided up by initial letter in the English alphabet. So far, so good. But wait, letter frequency isn't even, so some machines are going to get way more records than another. Here's one initial letter frequency sequence: The first letter of an English word, from most to least common: t o a w b c d s f m r h i y e g l n p u v j k q z x https://en.wikipedia.org/wiki/Letter_frequency Maybe you want to split "T" onto three machines: T Ti To Just guessing there on the splits. (The the dvisions would depend very much on the particular data set.) Now how does a binary search help you? Because you don't *care* about an exact match, you're just looking for the nearest match. So if you word is Tuesday, you should hit the "To" machine and if your word is "Table" you should hit the "T" machine, and so on. Okay, that was a pretty meandering and somewhat distracting way to say "sometimes the goal of a binary search is to find the nearest match." I have a particular love of algorithms that find "nearly" rather than "exactly".... For anyone with an interest in algorithms and a bit of time to waste, I recommend heading down the hashing rabbit hole. If you already understand hash tables, the interest bits are hash trees and distributed hashes. These two are both quite interesting: https://en.wikipedia.org/wiki/Consistent_hashing https://en.wikipedia.org/wiki/Rendezvous_hashing ********************************************************************** 4D Internet Users Group (4D iNUG) FAQ: http://lists.4d.com/faqnug.html Archive: http://lists.4d.com/archives.html Options: http://lists.4d.com/mailman/options/4d_tech Unsub: mailto:[email protected] **********************************************************************
