# Bubblesort, Binary Search, and Pointers

## Part 1: Bubblesort and Binary Search

1. `L = [7, 32, 2, 19, 3]`. Write down the array after every iteration of the
outer loop of Bubblesort.

2. `L = [3, 5, 10, 12, 39, 40, 68, 92]`. Write down the values of `low` and
`high` at the beginning of every iteration of binary search as you search for:
  - 19
  - 40

3. Suppose you had a list of 1,048,576 sorted integers. How many iterations of
binary search would be necessary to find an element? What if you had twice
that many (2,097,152)? Four times that many (4,194,304)?

4. Suppose you wanted to find if an element is in an *unsorted* list. First,
make sure you understand why binary search would not work in that setting.
Second, one approach would be to run the linear search algorithm from the
notes. Another would be to first sort the list with bubble sort, and then run
binary search. What would be the runtimes of the two approaches? 

5. Suppose you wanted to find if there were duplicate values in an unsorted
list (that is, whether any number appears more than once). One approach would
be to use `has_duplicate()` from [our previous homework](02BigO/hw). Another
would be to first sort the list using bubblesort, and then iterate along the
sorted list to see if any elements were identical to their adjacent members
(because in a sorted list, any duplicate values would be next to each other).
What is the runtime of each approach?

## Part 2: Pointers and Arrays

1. Consider the following Python code:

```python
list1 = [10, 20, 30]
list2 = [40, 50, 60]
list2 = list1
list1[0] = 99
print(list2)
```

Without running the code, what do you expect the output of `print(list2)` to
be and why?

[Solution set](algOgPtrsSoln)