## CS 245 Lecture 10 – Binary Search and Recursion

### 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

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

The slipper fit the fifth foot

“What magic!” they thought