# Module 08: Searching and Sorting

# Part 1 - Warm up questions

# Suppose you are searching in the list L = [2,5,10,15,22,29].
# How many iterations are required when searching for the following values in L
# (i) 2 (ii) 15 (iii) 29 (iv) 0 (v) 30
# (a) When using Linear Search? 
# (b) When using Binary Search? 



# Suppose you are trying to sort the list L = [20,15,5,25,0,10].
# After two iterations of one sorting algorithm as discussed in class,
# the list has been mutated to 
# (A) [5,15,20,25,0,10]
# After two iterations of another sorting algorithm as discussed in class,
# the list has been mutated to 
# (B) [0,5,15,25,20,10]
# The two sorting algorithms were Selection sort and Insertion sort. Which
# algorithm resulted in the mutated list (A)? Which resulted in (B)?

# Trace through the provided implementation of mergesort for the list
# [20,15,5,25,0,10]

# Part 2 - Extra Practice


#Problem 1:
# a)
# Rewrite linear_search to consume a list of values and a search
# value, and return the index of the search value in the list if it is
# there, and produce False otherwise.
# b)
# Rewrite binary_search to consume a sorted list of values and a search 
# value, and return the index of the search value in the list if it is there,
# and return the position of where the search value would be in the list 
# if it not in the list. For example, binary_search([2,4,6,8,10],8) => 3
# and binary_search([2,4,6,8,10], 5) => 2.   

# Videos for sorting techniques:
# Selection sort
# https://www.youtube.com/watch?v=LriMvv9qDrk
# Insertion sort
# https://www.youtube.com/watch?v=ROalU379l3U
# Mergesort
# https://www.youtube.com/watch?v=XaqR3G_NVoo
#
# No additional sorting code for practice. 
# Check out the quicksort technique in the tutorial. 
# Ensure that you understand how (and why) each of 
# the sorting techniques covered in class work.