Bubblesort, Binary Search, and Pointers Solution

Contents

Bubblesort, Binary Search, and Pointers Solution#

Part 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]

  1. 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

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

  2. 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.

  3. 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.

Contents