teaching machines

CS 145 Lecture 37 – Binary Search

December 14, 2016 by . Filed under cs145, fall 2016, lectures.

Dear students,

We close our semester today with a reading from Jeremy Kubica’s Computational Fairy Tales. It demonstrates an algorithm that I think is beautiful: the binary search. We will illustrate the algorithm and implement it to help code up a dictionary.

I think this algorithm demonstrates a significant point. This ultra-fast algorithm wasn’t the computer’s idea. It would be just as happy to perform linear searches. The good idea, the intelligence, was ours. The computer is not really a calculator; we’re the ones writing the expressions. It’s not a chef; we’re the ones organizing code into reusable chunks. It’s not a philosopher; that was us wondering something about are data. It’s not a pilot; that was us directing it from the observation tower. It’s not a factory worker; that was us avoiding mindless repetition. It’s not a scribe; we told it what to read and write. It’s not a creator; we are. The computer only amplifies ideas that you have in your head. This class has been about getting those ideas out to the machine.

Here’s your TODO list for next time:

See you next class!


P.S. It’s Haiku Wednesday!

The prince sorted them
The slipper fit the fifth foot
“What magic!” they thought

P.P.S. Here’s the code we wrote together…


package lecture1214;

public class NoDictionaryException extends RuntimeException {



package lecture1214;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Dictionary {
  private ArrayList<String> words;

  public Dictionary() {
    words = new ArrayList<String>();
    File dictionaryFile = new File("/usr/share/dict/words");
    try {
      Scanner in = new Scanner(dictionaryFile);
      while (in.hasNextLine()) {
    } catch (FileNotFoundException e) {
      throw new NoDictionaryException();

  public boolean containsLinear(String maybeWord) {
    for (String word : words) {
      if (word.equals(maybeWord)) {
        return true;
    return false;

  public boolean containsBinary(String word) {
    int first = 0;
    int last = words.size() - 1;

    while (first <= last) {
      int mid = (first + last) / 2;
      int order = word.compareTo(words.get(mid));
      if (order < 0) {
        last = mid - 1;
      } else if (order > 0) {
        first = mid + 1;
      } else {
        return true;
    return false;


package lecture1214;

import lecture1205.Stopwatch;

public class DictionaryTester {
  public static void main(String[] args) {
    String[] maybeWords = { "splatbot", "walnut", "chris", "johnson", "sorted", "middle", "sordid", "aah", "sophisticated", "sponge boat", "honorable", "mentions", "zipper", "fod", "precede", "wherefore", "ballerina", "ballerino", "dog", "hippopotamus", "gland", "seventeen", "balrog", "fashion", "pumpkin", "copper", "slar", "foo" };
    Dictionary dictionary = new Dictionary();
    Stopwatch timer = new Stopwatch();
    for (String word : maybeWords) {
      System.out.println(word + " -> " + dictionary.containsBinary(word));