# teaching machines

## CS 245 Lecture 10 – Binary Search and Recursion

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

### Agenda

• what ?s
• 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.

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

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