# CS21: Quiz 5 Study Guide

### In addition to the concepts below, you should also know the concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4. Many of the earlier concepts -- especially functions -- are fundamental to what we've been studying recently.

#### You should be able to define and explain the following terms:

• Searching: linear and binary search

#### You should understand and be able to use the following Python concepts:

• swapping two values in a list
• searching algorithms
• complexity (big O, number of steps) of searching algorithms
• string comparisons ("alice" < "zelda")

#### Practice problems:

1. True/False questions 1-4 on page 460 (Chapter 13)
2. Multiple choice questions 1, 2, and 6 on page 461 (Chapter 13)
3. Discussion question 1 on page 462 (Chapter 13)
4. Write a function to return the index of the smallest item in a given list.
5. Show the values for low, high, and mid for each step in searching the list L for the value x using binary search.
```x = 99
L = [-20, -12, -4, 1, 7, 44, 45, 46, 58, 67, 99, 145]     low   mid   high
----------------

```

6. Given the following definition:
```   ls = ["fish", "squirrel", "cat", "dog", "monkey", "pony"]
```
What are the value and type of the following expressions:
```  (1) ls[3] > "apple"
(2) ls
(3) ls[3]
(4) ls[3][1]
(5) 'b' < 'f'

```