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.
The morning's news was nothing short of dismal. King Fredrick had only been awake for twenty minutes when he decided that today was going to be awful. It had started manageably enough, with his head butler informing him that his favorite crown was still being polished and was not available. However, that news was quickly followed by his chief knight, Sir Braver, informing King Fredrick that a dragon was now terrorizing his kingdom.
"Tell me what happened," commanded the king in a weary tone. He hated dragons.
"There is a dragon," declared Sir Braver.
"You have already told me that part. Now tell me what has happened. Has anyone seen this dragon? Has it attacked anyone?" prompted the king.
“Yes, sir. We have received six confirmed sightings. Farmer McDonald has lost his prize cow."
"The one that won last year’s competition?" inquired the king. If he recalled correctly, it was a sizable cow and would be a perfect target for the dragon.
"Yes, sir," answered the knight.
The king sighed. The story sounded like a textbook dragon attack. Soon the dragon would eat half the cows in the kingdom. "Well, you had better take the dragon hunter and get rid of the dragon."
"But sir, no one knows where the dragon is. How shall we hunt it?" asked the knight.
"Really?" the king asked, surprised that his head knight did not know how to hunt a dragon.
Sir Braver remained silent.
"Find the last farm that it attacked,” said the king. "Dragons take long naps after each meal, so you have time to catch it there.”
"But sir, how will we know where that is?" asked the knight.
"Have you studied dragon attacks at all?" the king asked. "There is an order to these attacks. Dragons are smart. They eat the biggest cow in the area, then the second biggest, then the third, and so forth. They keep eating smaller and smaller cows, until the only remaining cows are too small to be worth the bother. Then the dragon goes on to the next kingdom."
"But sir…" started the knight.
"Use the rankings from last year's cow competition!" cried the king, losing his patience. "They have a sorted list of the largest cows!"
"Ah. Of course, sir. We shall work down the list until we find the dragon!" confirmed the knight.
The king nodded, relieved that the knight was finally thinking on his own. Sir Braver and the dragon hunter would visit the each of the farms on the list, in order, and find the dragon. Even as he tried to comfort himself with this thought, warning bells went off in the king's head.
"Not down the list," the king admonished. "Do you know anything about searching?"
The knight looked confused. He had been certain that he was on the correct track. "But sir, I don't understand" he said.
"How long does it take you to travel between farms?" asked the king.
"A few hours, sir."
"How many farms are on the list?"
"Maybe a hundred."
"That means that it could take you hundreds of hours. By that time, the dragon will have eaten more cows. It might even be gone by then."
"But, sir…"
"Use binary search," commanded the king.
"Binary search, sir?" asked Sir Braver, regretting having fallen asleep in his 'Algorithms for Knights' class.
"Start in the middle of the list and check whether the cow is still there. If it is still there: rip the list in half, throw away the bottom half, and repeat the process on the top half of the list. If the cow is gone: rip the list in half, throw away the top half, and repeat the process on the bottom half of the list. Each time you visit a farm, rip the list in half and concentrate your search on only one of the two halves."
"But sir, that sounds complex," protested Sir Braver.
“It is not," argued the king. "It is simple. If the cow in the middle of the list is still at the farm, then so are all the cows below it on the list. That is how dragons eat. It is not going to eat a smaller cow first. That would be absurd.
“On the other hand, if the cow is missing, then so are all the cows above it on the list. Dragons do not skip around lists randomly. There is an order to these things."
“What if the dragon moves while we are searching?” asked the knight.
Finally, a reasonable question. “Your search effectively tracks two bounds: the smallest cow that you know has been eaten and the largest cow that you know has not been eaten. If you get to a point where those bounds are next to each other on the list, and you do not see a dragon, then proceed to the largest uneaten cow and wait there.”
"But sir, how is that any faster than just scanning down the list?" asked the knight.
The king sighed, again. His confidence in the knight’s ability to handle this task was eroding rapidly. "If the dragon has attacked 45 farms, how long will it take you to scan those farms? 90 hours? But in the case of binary search: after the first farm you will have ruled out 50 farms on the list -- one way or another. After the second farm, you will have ruled out another 25. Each time, you are cutting the problem in half. In fact, you can find the dragon after checking only 7 farms."
The knight nodded, yet looked unconvinced. "But sir, are you sure?"
The king screamed. "Of course I am sure! I am the king! And, further, every idiot knows that binary search is a logarithmic time algorithm while scanning down a list is a linear time algorithm. NOW GO AND GET THAT DRAGON!"
For the first time in his long career as a knight, Sir Braver ran away. He told himself that he was running in order to carry out the king's orders as quickly as possible. But in truth, the king looked really mad.
As he watched his top knight clank noisily down the hall, the king decided that it was indeed time to go back to bed.
For more on binary search also see Binary Searching for Cinderella.
About 16 hours later, Sir Braver returned dispirited, covered in mud, but suspiciously soot-free. He fell to his knees before the king.
ReplyDelete"Sire! We have failed you. I shall forsake my coat of arms, repudiate my grade in Algorithms for Knights, and live henceforth as a nameless knight errant."
The king pounded his fist in frustration. "Damn! But.. what happened, Sir Braver? How many of your men survived? Where was the dragon?"
The knight stood back up but kept his head bowed as he told the tale. "We checked farm #50. There, the cow was safe and well. So, we proceeded to farm #25 according to this algorithm your scribe wrote out for us. Farm #25's cow had been eaten, as had farms #37, 43, 46--my own tenants' farm, sire! woe is me!--48, and 49.
"Elated, we rushed back to farm #50 knowing that the dragon would strike there next. Sadly, when we arrived we discovered our mistake. Farm #50's cow was also dead, sire! What we had previously taken for a living cow must, in fact, have been a pile of gnawed and fire-blackened bones. We failed at the most basic element of your algorithm, the test for liveness.
"As penance for my failure, I am also visiting the Royal Surgeon to check my eyes, ears, nose, and left hand--which I must have foolishly used to tenderly pat that adorable, formerly 3820 lb pile of dragon remnants between its gaping ocular orbits."
The king looked everywhere but at his stolid knight. "Er.. yes. You must indeed have failed. It was an excellent algorithm. Guards, take this knight errant away, and bring in Sir Brave."
Having dispatched the comparative knight Braver in favor of the absolute knight Brave, the king charged him with an eerily familiar task.
"Sir Brave: head to the farm on the list with the smallest cow. If it's alive, head to the farm with the next larger cow. Keep going until you FIND that dragon."
"Yes, Sire!" Sir Brave clashed his sword to shield and stalked out.
{That} thought the king {surely cannot fail. Can it?}
Just added: a new story about binary search:
ReplyDeletehttp://computationaltales.blogspot.com/2011/12/binary-searching-for-cinderella.html
Based on some great feedback on this story (including one of the comments above), I have modified it to be a bit tighter in terms of finding the dragon.
ReplyDelete"..the smallest cow that you know has been eaten and the largest cow that you know has not been eaten. If you get to a point where those bounds are next to each other on the list, and you do not see a dragon, then proceed to the largest uneaten cow and wait there."
ReplyDeleteYou might want to exchange smallest and largest here.
Reisender, good question. In this case do want to track the smallest eaten cow (because it rules out all larger cows) and the largest uneaten cow (because it rules out all the smaller cows). When those bounds are next to each other, you have the last cow the dragon has eaten and the next cow it will eat. The next cow it will eat is the largest uneaten one one the list, so you can wait for the dragon there.
ReplyDelete