# Bubblesort, Binary Search, and Pointers Solution

## Part 1

1.
```
[7, 32, 2, 19, 3]
[7, 2, 19, 3, 32]
[2, 7, 3, 19, 32]
[2, 3, 7, 19, 32]
[2, 3, 7, 19, 32]
[2, 3, 7, 19, 32]
```

2. Searching for 19:
```
low: 0 high: 8
low: 0 high: 4
low: 2 high: 4
low: 3 high: 4
```

Searching for 40:
```
low: 0 high: 8
low: 4 high: 8
low: 4 high: 6
low: 5 high: 6
```

3. 20 (find by repeatedly halving until you get to 1, or by calculating
$\log_2(1048576)$. 21. 22.

4. Binary search does not work on unsorted lists because we assume that if the
element `mid` is too small, everybody before it must also be too small (and
similarly if it's too big). The linear search would be $O(n)$. Sorting, and
then running binary search would be the runtime of bubblesort ($O(n^2)$) plus
the runtime of binary search $O(\log(n))$. The larger of those terms is
$O(n^2)$, so that is the runtime of the combined operation.

5. The runtime of `has_duplicate()` is $O(n^2)$. To sort with bubblesort and
then iterate looking for duplicate consecutive elements would be $O(n^2)$
followed by $O(n)$, for a total runtime of $O(n^2)$.

## Part 2

1. It would be `[99, 20, 30]`. The line `list2=list1` makes it so `list2` points
to the same thing as `list1`, so a change to that underlying list changes the
results of printing either.