» CS 145 Lecture 37 – Binary Search

CS 145 Lecture 37 – Binary Search

December 14, 2016 by Chris Johnson. 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:

I will run the amnesty homework 7s tomorrow morning. If you have homework 7 fully completed and have emailed me before 6 AM to announce its completion, you may resubmit exactly one of homework 5 or homework 6. Please tell me in your email which you’d like regraded and have it resubmitted before Monday. Please do not expect further amnesty after these first two amnesty periods. Accidents and screwups are welcomed in this class, and chances to make good on them have been built in from the very beginning.
The final exam is in our regular classroom on Wednesday from 3-4:50 PM. It will follow a similar format to the previous exams, but include objects and lists.

See you next class!

Sincerely,

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…

NoDictionaryException.java

package lecture1214;

public class NoDictionaryException extends RuntimeException {

}

Dictionary.java

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()) {
        words.add(in.nextLine());
      }
      in.close();
    } catch (FileNotFoundException e) {
      throw new NoDictionaryException();
    }
    Collections.sort(words);
  }

  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;
  }
}

DictionaryTester.java

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();
    timer.start();
    for (String word : maybeWords) {
      System.out.println(word + " -> " + dictionary.containsBinary(word));
    }
    System.out.println(timer.stop());
  }
}