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

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?