Binary search is an algorithm for efficiently finding a target value within a sorted list. The algorithm maintains a shrinking search window. It narrows down that window by repeatedly ruling out half of the remaining search space. At each step, the algorithm checks the middle item in the current window and compares it with the target value. If the value in the middle is less than the target, you can rule out the lower half of the window. If the value is greater than the target, you can rule out the upper half. This process repeats until the target item is found or the window shrinks to a single (non-matching) item.
Alfred Charming could not understand his cousin, Prince Charming. For the last sixteen hours, the prince had babbled continuously about his magical, life-changing night at the ball. The prince had met the girl of his dreams, and she was perfect. Yet, the night had ended with that very same girl running from the party and diving into an oversized pumpkin on wheels. Alfred was certain that was a bad sign. It ranked somewhere between a fake headache and an actual slap to the face. Despite this setback, his cousin was still obsessed with finding this mystery girl. The prince desperately clung to her glass slipper, determined that it would lead him back to her.
Of course, Alfred could excuse his cousin's romantic notions. He had witnessed first-hand the disaster of last month's ball. He had been there to comfort the prince through the tears that had followed. His cousin was under tremendous pressure to marry, but finding his princess had been far from smooth. For now, at least, the prince could bask in the delusional glow of a magical night of dancing and small talk with a mysterious party goer.
However, Alfred could NOT excuse his cousin's flawed strategies for finding the woman of his dreams.
"I shall go forth to every house and find the owner of the slipper," proclaimed Prince Charming.
"Are you crazy?" objected Alfred. "That would take weeks. And you have to help them try on a slipper made of glass. Think of the germs. It is a health nightmare."
"I must find my true love," protested the prince.
"Fine," said Alfred. "I am still not sure why, but let's say that you do need to find this girl. You don't have to go to every house."
"I must be thorough," said the prince.
"You can still be thorough using a good algorithm," argued Alfred. "Trade data for time."
"Data? Time?" asked the prince.
Alfred thought for a moment. "Ye Old Foot Shoppe has a list of everyone in the kingdom's shoe size. Have them compute the size of the glass slipper, and you can look for a match on their list. They keep sizes with two decimal points of precision, so there will only be a few matches at most. I bet the slipper is around a size 5.75. And, if you do happen to find a few matches, you can go try them all."
The prince did not look convinced. "Spend the day searching for numbers in a list? How is that romantic? It sounds like hours of dreadful effort."
"The store's list is already sorted," explained Alfred. "You can use binary search to find a match. It is better than days of trying to fit the same glass slipper on different feet."
"Binary search?" The prince's education had not required an algorithms class.
"The search algorithm," said Alfred.
The prince continued to stare blankly back at Alfred.
"You can do it using your fingers," explained Alfred. "Use two fingers to track where in the list the slipper's owner could be. One finger indicates the start of the range, and one finger indicates the end of the range. Let's keep it simple and call them the 'start' and 'end' fingers respectively. If you do the search correctly, the matching shoe size is always somewhere between (or possibly under) your fingers."
"Initially, the entire list is under consideration," continued Alfred. "So start with your 'start' finger at the beginning of the list, and your 'end' finger at the end."
"Then I use my fingers to scan through the whole list?" interrupted the prince. "What do I do? Move one finger up then the other down? Sounds dreadful. I might get a paper cut!"
"No," answered Alfred. "Then you do binary search. First, you look at the list entry halfway between your fingers. Call that the 'middle' entry, because it will be in the middle. Second, you can compare the middle value to the one from the shoe. And third, you move one of your fingers depending on the value of the middle entry.
"There are only three cases to consider:
1) If the glass slipper is smaller than the middle value, you only have to work on the 'smaller' half of the list. Move the 'end' finger to where the middle value is, because all of the entries after the middle are too large to match. The matching size will still be between your two fingers.
2) If the glass slipper is larger than the middle value, you only have to work on the 'larger' half of the list. Move the 'start' finger to where the middle value is, because all of the entries before the middle are too small to match. Again, the matching size will still be between your two fingers.
3) If the middle value matches the slipper's size, you are done. You found a match. Yay."
"Your method only eliminates half the list," objected the prince.
"You repeat the process on the remaining half of the list," sighed Alfred. "Pick the entry halfway between your two fingers and call that the new 'middle'. Compare the middle value to the shoe size and use the same logic to eliminate half the list. After each step, you cut the size of the list in half, and still guarantee that the target value is between your fingers."
"When do I stop?" asked the prince. "When do I find my princess?"
"You stop when you find a match," answered Alfred. "Unless, of course, there is no match. If you reach a point where there is nothing left to search, then the list does not contain a match."
"How will I know that there is nothing left to search?" asked the prince.
"There is nothing left to search when there are no new values between your fingers. This can happen if both fingers point to the same place or if they are right next to each other. As I like to say: 'If your fingers touch, you are out of luck'."
"That does not rhyme. It would sound better if it rhymed," observed the prince. "More importantly, what if my princess's name gets skipped? Your algorithm involves big jumps early on. I am not sure that I could survive losing her."
"It won't skip her," answered Alfred. "At each step we guarantee that if there is a match, it is between your fingers. However, it is true that binary search will only give you ONE match and it might not be the first one. If you want all the matches, which you do, you will need to check the list entries near the match. Scan outward from the match."
The prince nodded solemnly. "I am sure that there will only be one match. My princess is perfectly unique."
Alfred stifled back a thousand comments and smiled politely.
After a moment, the prince continued. "While your idea has merit, I believe that I shall stick to my original plan. I shall go forth to every house and test the slipper."
"Why?" asked Alfred. "What if someone is not home? What if your mystery girl is locked in a basement by evil family members? What if someone breaks the slipper? That plan has so many problems."
The prince smiled. "I want the people to know that I am searching for my true love. If I use your binary search, I miss the excitement of the search. Binary search is not romantic."
Alfred sighed. He did not have an argument to counter that.
-------------------------
For more about binary search, see Hunting Dragons with Binary Search.
Love this.
ReplyDelete