On my first day of class at Harvard, at the end of a lackluster economics lecture, I was shoving my stuff into my backpack when electronic music started blasting through the speakers. The beat seemed to shake the chandelier. A sans serif logo appeared projected at the head of the room: CS50, Introduction to Computer Science. I had nowhere to be, so I stayed. At seven minutes after the hour (“on Harvard time”) the lecturer, David Malan, tested the mic clipped to his black sweater and strode into the spotlight to teach us how to program.
He demonstrated our first algorithm—binary search—by looking for the name Mike Smith in a phone book. Malan flipped to a spot in the middle: too early in the alphabet. “So what do we do?” he asked. A row of teaching fellows onstage ripped tomes in half and threw them to the floor. The audience gasped. Malan’s assistants picked new pages and repeated the procedure. Finally, the head teaching fellow held up a single page, triumphant. The crowd applauded and hollered.
It took less than a minute, although Malan drew it out for dramatic effect. If the phone book had 1,000 pages, it only took an average of 10 tearings to find the right one: 500 pages, then 250, 125, 62, 31, 16, 8, 4, 2, then 1. He said something about logs—1024 log base 2 is 10—but I couldn’t think about math, only about magic. I stared at the resulting single page slack-jawed, transfixed.