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

# # Lecture 10 : Exercices
# 
# 

# # 1. List review
# 
# ### 1.1
# 
# Create a list called `my_list` that contains 5 integer values.

# In[ ]:





# ### 1.2
# 
# Print every element in that list (`my_list`) using a `for` loop

# In[ ]:





# ### 1.3

# The function `minimum(L)` finds the minimum element in a list `L` :
# ```python
# def minimum(L):
#     min_so_far = L[0]
#     for element in L:
#         if element < min_so_far :
#             min_so_far = element     
#     return min_so_far
# ```

# Now, write a function `maximum(L)` that takes a list of integers `L` and returns the largest integer in that list.

# In[ ]:





# ### 1.4 

# Write a **recursive** function `recursive_max(L)` that takes a list of integers `L` and returns the largest integer in that list.

# In[ ]:





# # 2. Selection Sort
# 
# ### 2.1
# 
# Write a function `min_index(L)` that takes a list `L` and returns the index of the smallest integer in `L`. Hint: you should use a `for` loop!

# In[ ]:


def min_index(L):
    # Complete the function here!
    return 

print(min_index([1, 2, 3, 4]) == 0)
print(min_index([55, 66, 33, 22]) == 3)


# ### 2.2
# 
# Here is the iterative implementation of selection sort that you saw in lecture:

# ```
# 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
# ```

# ### 2.3 
# 
# Write a **recursive** function of selection sort called `recursive_sort(L)`. Hint: you should use the function `min_index(L)` from 2.1:

# In[ ]:


def recursive_sort(L):
    # Complete the function here
    return


# In[ ]:





# 
# 
# # 3. Insertion Sort

# ### 3.1 
# 
# You're given the list  `L = [1, 2, 4, 5]`. Using slicing, insert the element `3` in the list such that `L` remains sorted.

# In[ ]:


L = [1,2,4,5]


# ### 3.2 
# 
# Write a function `less_print(L, k)` that takes a sorted list `L` and prints all the elements of `L` that are less than `k`.

# In[ ]:





# ### 3.3 
# Write a function `find_position(L, k)` that finds the index of the greatest element in `L` that is less that `k` : <br/>
# For example : <br/>
# `find_position([1, 2, 4, 5], 3)` should return `1` because `2` is the greatest element less than `3` and is in index `1`.<br/>
# `find_position([9, 10, 11, 13, 14], 12)` should return `2`.

# In[ ]:





# ### 3.4 
# 
# Using `find_position(L, k)`, write a function `insert(k, L)` that inserts `k` into a sorted list `L` so that the list stays sorted. 
# 
# As input the function takes `k`, the element to insert and `L`, the sorted list to insert `k` into.
# 
# For example:
# ``` 
# insert(5, [4,6,8,9]) == [4,5,6,8,9]
# insert(8, [2,5,6,9,10,34])  == [2,5,6,8,9,10,34]
# ```

# In[ ]:





# ### 3.5
# 
# Write a function `insertion_sort(L)` that takes a list `L` and inserts elements of `L` in a new list using `insert(k,L)`. <br/>
# 
# Here is how the function should work : <br/>
# `L = [ 1, 4, 5, 3, 2, 7, 0]`  and `new_list = [] `<br/>
# `L = [ 4, 5, 3, 2, 7, 0]`  and `new_list = [1] `<br/>
# `L = [ 5, 3, 2, 7, 0]`  and `new_list = [1, 4] `<br/>
# `L = [ 3, 2, 7, 0]`  and `new_list = [1, 4, 5] `<br/>
# `L = [ 2, 7, 0]`  and `new_list = [1, 3, 4, 5] `<br/>
# `L = [ 7, 0]`  and `new_list = [1, 2, 3, 4, 5] `<br/>
# `L = [ 0]`  and `new_list = [1, 2, 3, 4, 5, 7] `<br/>
# `L = []`  and `new_list = [0, 1, 2, 3, 4, 5, 7] `<br/>
# 

# In[ ]:





# # 4. Median Finding
# 
# ### 4.1 
# 
# The **median** element of a list `L` is the element that is smaller or equal to half of the elements in `L`. <br/>
# 
# For example, <br/>
# The median of `[1, 2, 4, 5, 6]` is `4`. <br/>
# The median of `[7, 5, 4, 1, 3, 2, 4, 9, 9, 7]` is `5`. <br/>
# 
# Write a function `median(L)` that takes a list `L` and returns the median of the list `L`.
# Hint : The list `L` is not sorted. You need to use your sort function from 3.1 (`recursive_sort`)

# In[ ]:


def median(L):
    # Complete the function here
    return 

print(median([1, 2, 3]) == 2)
print(median([1]) == 1)
print(median([5, 4, 1, 4, 3]) == 4)


# # 5. Sorting points (optional)
# 
# ### 5.1
# 
# We want to sort a list of points (x, y) in a plane. For example `L = [[2, 3], [4, 5], [6, 3], [4, 0]]`.
# 
# We define the order of the points as `[a, b] < [c, d]` if `a+b < c+d`. In other words, a point is smaller than an other point if the sum of x + y is smaller. 
# 
# So according to this ordering, the list `[[4, 0], [2, 3], [6, 3], [4, 5]]` is a sorted one. <br/>
# 
# Modify the function `min_index(L)` from 2.1 so that `recursive_sort` from 2.3 works for sorting points.

# In[ ]:





# # 6. Binary search

# In binary search, we look for an element x in a **sorted list** by first comparing x to the midpoint of the list. If `x < midpoint`, search the left half of the list. Otherwise, search the right half. Then repeat until we either find x or there are no elements to look through.

# ## Classic binary search

# The code below can be used to play the _Guess The Number_ game. Let's say you have a number x and you want your friend to guess it. They make a guess and then you tell them if your number is less, greater or equal to their guess.
# 
# Try playing the game by running the code below using different inputs. 

# In[ ]:


#This code returns the number of guesses made
def guess(x, left, right):
    
    if x > right or x < left:
        print("Invalid number!")
        return -1
    
    mid = (left+right)//2
    
    print("My guess is:", mid)
    
    if mid == x:
        print("Exactly!\n")
        return 1
    
    if mid > x:
        print("But that is too big!\n")
        return 1 + guess(x, left, mid-1)
    
    if mid < x:
        print("But that is too small!\n")
        return 1 + guess(x, mid+1, right)
    

print( guess(56, 1, 100) )


# ## 2.2 

# What are the **left** and **right** values for each of the 4 guesses made in  `guess(56,1,100)` ?

# In[ ]:





# ## 2.3 

# What are the **left** and **right** values for each of the guesses made in  `guess(1,1,100)` ?

# In[ ]:





# ## Iterative Binary Search
# 
# Here is an implementation of binary search using a `while` loop. Run this cell before continuing:

# In[ ]:


def binarySearch(a, x):
    computer_num = 3
    cnt = 0
    left = 0
    right = len(a) - 1
    
    while left+1!=right:

        mid = (left+right)//2

        cnt += 1

        if a[mid] == x:
            break

        if a[mid] > x:
            right = mid - 1

        else:
            left = mid + 1

    print("Number of guesses:", cnt)
    print("Your number is:", a[mid])
    return cnt

binarySearch([1, 2, 4, 6, 7, 10], 4)


# ## 3.1

# Given the array `[−1,3,6,10,15]` if we are searching for `10` what values of the array do we look at? Put a `print` statement in the function `binarySearch` above to check if you are correct.
Type your answer here:

# ## 3.2 
# What are the values of  **left**  and  **right**  for `binarySearch([-1, 0, 1, 3, 5, 7, 11], 5)`?
Type your answer here:

# ## 3.3
# 
# What will happen if we run `binarySearch([1, 9, 8, -1, 4, 11], 4)`? Why does this not work? How would you fix it?
Type your answer here:

# # 4.

# Given a sorted list of strings `L`, and an element in the list `t`,  write a function called `findInd(L, t)` that uses binary search to determine the index of `t` in `L`.
# 
# ```findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'tape') == 3```
# 
# ```findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'zebra') == 5```
# 
# ```findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'ape') == 0```

# In[ ]:


def findInd(L, t):
    # Complete the function here!
    return
    


    
print(findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'tape') == 3)
print(findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'zebra') == 5)
print(findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'ape') == 0)


# ## Optional Challenge Problems:

# ### Linear Search
# 
# Given a list `L` and a value `x`, use a `for` loop to find the index of the first time that `x` appears in `L`.
# If `x` does not appear in `L`, return `-1`.

# In[ ]:





# ### Local maximum.
# 
# You are given an unsorted list `L` of nonnegative integers. For example,
# `L = [200, 500, 30, 0, 1, 4]`
# 
# Find any number in the list that is greater than the numbers to the left and right of it.
# Return the index of the number.
# For example,
# `localMax(L)` should return `500`.
# 
# The first element is a local max if it is greater than the second element.
# The last element is a local max if it is greater than the second to last element.
# 
# 
# For example:
# 
# `L = [1, 2, 3, 4, 5]`
# `localMax(L) == 5`.
# 
# Hint: Use recursion.

# In[ ]: