#!/usr/bin/env python
# coding: utf-8

# # 1. Searching

# We will start by looking at how the Binary Search Algorithm works!
# 
# Reminder:
# 
# ```python
# def binSearch(L,s):
#     start = 0
#     end   = len(L)
#     while start<=end:
#         mid = (start+end)//2
#         if s<L[mid]: end = mid-1
#         if s>L[mid]: start = mid+1
#         if s==L[mid]: return mid
#     return -1
# ```
# 

# ### 1.1
# 
# Let's start with the list `L=[0,1,2,3,4,5]` and `s = 4`
# 
# Imagine we wanted to check if `s` is in this list. The values of `mid` in this case will be 2 and 4.
# 
# Do the same, for the following lists:
L = [0,1,2,3,4,5,6,7,8,9], s = 3
step 1: mid = 
step 2: mid = 
step 3: mid = 
step 4: mid = L = [2,4,6,8,10,12,14,16,18,20], s = 20
step 1: mid = 
step 2: mid = 
step 3: mid = 
step 4: mid = 
# ### 1.2
# Write a function that given a list `L` and a number `n`, returns the position of that number in the list.

# In[ ]:


def mySearch(L, n):
    for i in range(len(L)):
        if L[i] == n:
            return i
    return -1


# ### 1.3
# 
# Write a function that given a sorted list `L` and a number `n`, returns the position of that number in the list using Binary Search.

# In[ ]:


def myBetterSearch(L, s):
    # Write your code here
    


# Questions 1.2 and 1.3 ask you to solve the same problem but with different algorithms. What is the complexity of each?
Complexity of 1.2:
Complexity of 1.3:
Explain:

# ### 1.4
# 
# Write a function that takes in two lists of strings, `L1` and `L2`. For every string in `L1`, check if it is in `L2`.

# In[ ]:


def inMyList(L1, L2):
    # Write your code here


# ### 1.5
# 
# Given that `L2` is sorted, do the same using Binary Search.

# In[ ]:


def inMyListBS(L1, L2):
    # Write your code here


# Questions 1.4 and 1.5 ask you to solve the same problem but with different algorithms. What is the complexity of each?
Complexity of 1.4:
Complexity of 1.5:
Explain:

# # 2. Sorting

# ### Selection Sort
# ```python
# def selection_sort(L):    
#     for i in range(len(L)):
#         min_idx = i + min_index(L[i:])
#         L[i], L[min_idx] = L[min_idx], L[i]
#     return L
# ```
# 
# 
# ![](selection_sort.png)

# ### 2.1
# 
# By hand show the steps of selection sort algorithm for the following lists:
L = [4,3,2,1,0]
step 1: 
step 2: 
step 3: 
step 4: L = [10,5,7,6,11,42,3,8]
step 1: 
step 2: 
step 3: 
step 4: 
step 5: 
step 6: 
step 7: 
# What is the complexity of selection sort? Keep in mind that `min_index` has $O(N)$ complexity.
Complexity of Selection Sort: 
Explain:

# ### Merge Sort
# 
# General Idea:
# 1. Sort the first $n/2$ elements to get a list $L1$ and the last $n/2$ elements to get a list $L2$.
# 2. Merge the two lists together to one sorted list.
# 
# Code:
# ```python
# def mergesort(L):
#     if len(L) <= 1: return L
#     m = len(L)//2
#     L1 = mergesort(L[:m])
#     L2 = mergesort(L[m:])
#     return merge(L1,L2)
# ```

# ### 2.2
# 
# By hand show the steps of merge sort algorithm for the following lists:
L = [10,5,7,6,11,42,3,8]
step 1: 
step 2: 
step 3: 
step 4: 
step 5: 
step 6: L = [4,3,2,1,0]
step 1: 
step 2: 
step 3: 
step 4: 
step 5: 
step 6: