teaching machines

CS 245 Lecture 10 – Binary Search and Recursion

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

Agenda

• what ?s
• think about this
• computational complexity
• binary search implementation
• recursion
  • times(char, int)
  • isEven
  • file finding
  • binary search

TODO

• Read chapter 5 through section 5.3 in Data Structures. The reading may be useful in the next lab.
• Write a recursive method that paints a Target logo—a red circle around a smaller white circle around a smaller red circle around a smaller white circle… Test out your method by writing a short JPanel subclass whose paintComponent method calls your recursive method.
• 1/4 sheet.

Think About This

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