1. Searching¶
We will start by looking at how the Binary Search Algorithm works!
Reminder:
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:
1.2¶
Write a function that given a list L and a number n, returns the position of that number in the list.
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.
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?
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.
def inMyList(L1, L2):
# Write your code here
1.5¶
Given that L2 is sorted, do the same using Binary Search.
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?
2. Sorting¶
Selection Sort¶
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.1¶
By hand show the steps of selection sort algorithm for the following lists:
What is the complexity of selection sort? Keep in mind that min_index has $O(N)$ complexity.
Merge Sort¶
General Idea:
- Sort the first $n/2$ elements to get a list $L1$ and the last $n/2$ elements to get a list $L2$.
- Merge the two lists together to one sorted list.
Code:
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: