teaching machines

CS 245 Lecture 10 – Binary Search and Recursion

February 20, 2014 by . Filed under cs245, lectures, spring 2014.

Agenda

TODO

Think About This

Your lab partner has a competing solution for an algorithm. You say, “I bet mine’s faster.” Your partner says, “I’ve got my watch here. We’ll let time decide the better solution.” This means of comparison seems flawed to you. Identity two or more problems with your partner’s suggestion.

Code

Suit.java

package lecture10;

public class Suit {
  public static final int HEARTS = 0;
  public static final int DIAMONDS = 1;
  public static final int CLUBS = 2;
  public static final int SPADES = 3;

  
}

SuitEnum.java

package lecture10;

public enum SuitEnum {
  HEARTS, SPADES, CLUBS, DIAMONDS
}

SuitRank.java

package lecture10;

public enum SuitRank {
  ACE(1),
  TWO(2),
  THREE(3),
  FOUR(4),
  JACK(10),
  QUEEN(10),
  KING(10);
  
  private int worth;
  
  private SuitRank(int worth) {
    this.worth = worth;
  }
}

SuitTester.java

package lecture10;

public class SuitTester {
  public static void main(String[] args) {
    printSuit(Suit.HEARTS);
    printSuit(-5);
    printSuitEnum(SuitEnum.HEARTS);
    printSuitEnum("SPADES");
  }
  
  private static void printSuit(int suit) {
    
  }
  
  private static void printSuitEnum(SuitEnum suit) {
    
  }
}

ArrayUtilities.java

package lecture10;

public class ArrayUtilities {
  public static int indexOf(int[] numbers,
                            int target) {
    int first = 0;
    int last = numbers.length - 1;
    while (first <= last) {
      int mid = (last + first) / 2;
      if (numbers[mid] > target) {
        last = mid - 1;
      } else if (numbers[mid] < target) {
        first = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] numbers = {
      42, 54, 93, 103, 100000
    };
    System.out.println(indexOf(numbers, 42));
  }
}

Haiku

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