Made by: Ryan, Daniel, Saaras, Will, and Andrew
Python lists Operations
Append function
From the Data Abstractions Unit we Learned about lists and how they can store multiple variables
Today we’re going to show you how to add items to lists utilizing the append option
lst = ["hi"]
lst.append("no")
print(lst)
['hi', 'no']
Insert function
- The insert function allows you to append items to different lists at a specific location.
- Let’s first understand how it may work through pseudocode
Exmaple 1
INSERT alist, pos, value INSERT alist, 1, “hi”
- Here the alist represents your list you want to append an item to
- The position is where on the list the item will be generated in respect to the current list
- Finally, the value is the item you’re adding to your list.
- So in the code provided below, in position 1 you insert the item “hi” into alist
Your turn!!!!
- Turn this pseudocode into python
- How may we want to implement this on python? Think back to the data abstraction unit.
- ( Hint: Think about the differences between psueodcode and python )
# ANSWER:
lst = ['yes', 'yes', 'yes', 'hi', 'no', 'yes']
# Inserting items to a specific list, remember python is 0 based on the items!!
lst.insert(5, "maybe")
lst.insert(1, "index 1")
print(lst)
['yes', 'index 1', 'yes', 'yes', 'hi', 'no', 'maybe', 'yes']
Remove function
- The remove functions allows you to remove specific items at a specific position on the list
Pseudocode example
- REMOVE aList, pos
lst = ['hi', 'no', 'maybe', 'yes']
print(lst)
lst.remove(lst[0])
print(lst)
## You can also access the list by the position, this is called list indexing
print(lst[0])
['hi', 'no', 'maybe', 'yes']
['no', 'maybe', 'yes']
no
Let’s do some Collegeboard exercises
- In the following list:
- nums = [65, 89, 92, 35, 84, 78, 28, 75]
- Figure out what the minimum number in the list, WITHOUT using the other methods and premade functions.
Second question:
- Let’s say we have a list called “animals” from a survey that stores whether or not they prefer “cats” or “dogs” as strings in this list.
- Transverse this list and tell me the total amount cats and dogs in the list
nums = [65, 89, 92, 35, 84, 78, 28, 75]
print(nums[3])
print("this number is the lowest number in the nums list")
## Your code here
print(nums[6])
print("this is the actual lowest number")
35
this number is the lowest number in the nums list
28
this is the actual lowest number
animals = ["cats", "dogs"]
animals.remove("dogs")
print(animals)
print("only one person works at this petshop and she likes cats.")
['cats']
only one person works at this petshop and she likes cats.
ITS BINARY SEARCH TIME
- By the end of this you should be able to know what binary search is
- What the time complexity of binary search is
- How to derive the time complexity for binary search
HOW DOES BINARY SEARCH WORK
- pay attention to the demonstration in the front
- volunteers will be called up
- candy if you participate
Binary search is like a guessing game where you halve your options at each step. Imagine you’re finding a name in a phone book:
- First Step: You open the book in the middle.
- Second Step: Is the name before or after the middle? You eliminate half of the remaining names.
- Repeat: Keep dividing until you find the name or run out of names to check.
- MAKE SURE YOUR LIST IS SORTED Binary search will not work if the list isn’t sorted
Because you’re halving the options each time, it’s super quick. If you have (n) names, it takes at most ( \log_2(n) ) steps to find a name. This efficiency, where the time it takes doesn’t increase much as the number of names in the phone book grows, is what makes binary search awesome! Binary search is also more optimal for searcihng compared to a linear search for anything that doesnt include small lists..
Demo Being shown above
The sorted list we have currently, has integers [1, 3, 4, 5, 13, 20], we are currently trying to find the index of the the integer 1 within the list
How it works is we start at element 0 for our left position and element 5 for our rightwards position
Our middle position becaomes 5 because ((5+0)//2)=3 so element 3
Our element 3 within the list gives us the integer 5
We then realize that oh 5 is greater then 3 so we have to move leftwards
Then to make the algorithm more efficient we move the r backwards 1 beacuse we have already checked at this point
So now we can reduce the list to [1, 3, 4]
Now we can repeat the same steps as before and find the middle of this list which is 3
We realize thats not equivalent to the integer 1, and our value is still too great
So we move the middle leftwards 1 positioon
AND BAM THATS HOW YOU CAN DO BINARY SEARCH
# example of binary search in python has a time complexity of O(n)
def binarySearch(arr, x):
l= 0 #our minimum element
r=len(arr) - 1 # our maximum element
while l <= r:
mid = l + (r - l) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
l = mid + 1
else:
r = mid - 1
return -1
sorted_list = [2, 5, 8, 12, 16]
target = 12
result = binarySearch(sorted_list, target)
print(result)
3
#Linear Search Approach in O(n)
def linear_search(target, sorted_list):
for o in range(len(sorted_list)):
if sorted_list[o]==target:
return(o)
#Does not have to be a sorted list for the sake of comparison I just made it sorted
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15] #worst case scenario for linear search is last item bc have to go through every item to find it
target = 7
result = linear_search(target, sorted_list)
print(result)
3
Using linear search make a list with elements [“eggs”, “milk”, “butter”, “cake”] Then randomize an element 1-4 within that list and find the index of it via linear search
#code here
import random
index = random.randint(0,3)
def search(end, strings):
for i in strings:
if i == end:
return(i)
strings = ["eggs", "milk", "butter", "cake"]
result = search(strings[index], strings) #index is the random number, so strings[index] gets the random string that we want to find
print(result)
print("the index is " + str(index))
butter
the index is 2
How big O Notation works in the context works in the case of search methods.
Lets first explain for linear search, because linear search only requires a iterative approach all we use is O(n), this is due to the loop infinitely going until it finds the element and then after that it doesnt do anything.
However binary search is special in this sense because you don’t actually have to go through an entire loop how you can picture this is by imagining a list with 1000000 integer values in it and my target value is 59223, binary search makes it so that you just divide the list by 2 until you find the element. It’s a lot faster then the iterative approach, where I keep going until I get to 59223 what this does is it allows me to speed up the time and memory usage I take. because I keep dividing the list by 2 allowing for me to form a logarithm because its just repetitive multiplication of 1/2 and then that makes it so that O(log(n)) becomes the time complexity for the Binary search algorithm.
HW TIME!!!!!!!!!!!!!!!!!! We want you guys to make a guessing game below, where utilizing binary search you can within a list of 100 sorted elemments find, a value that your code will randomize using random.randint(). We want you to also make it so every iteration output the number is higher up or lower until you actually get to the answer. We also want number of tries it took to guess the number. Points will be awarded for customizations and potential changes.
Extra credit (for above 95%): Send a screenshot on me to slack showing you can do this: https://codeforces.com/contest/1201/problem/C
#Code in here
import random
# function for binary search
def binarySearch(sortNumList):
minIndex = 0
maxIndex = len(sortNumList) - 1
while minIndex <= maxIndex:
middle = (minIndex + maxIndex)//2
if sortNumList[middle] == endNum:
return middle
elif sortNumList[middle] < endNum:
minIndex = middle
else:
maxIndex = middle
# create list of 100 random numbers
numList = []
x = 0
while x<100:
num = random.randint(0,100)
numList.append(num)
x += 1
sortNumList = sorted(numList)
print(f"This is the list in question with a length of {len(sortNumList)}: {sortNumList}.")
# pick random number to find using binary search
endNumIndex = random.randint(0,99)
endNum = numList[endNumIndex]
# call function and print result
output = binarySearch(sortNumList)
print(f"The target value was {sortNumList[output]} at index {output}")
This is the list in question with a length of 100: [0, 1, 1, 3, 6, 7, 8, 9, 11, 13, 13, 16, 17, 18, 19, 20, 20, 21, 22, 22, 24, 25, 25, 25, 26, 27, 27, 30, 30, 30, 31, 34, 34, 35, 35, 35, 35, 36, 37, 37, 38, 39, 39, 40, 41, 42, 44, 47, 47, 48, 48, 48, 49, 49, 51, 52, 52, 53, 54, 55, 56, 57, 58, 58, 60, 61, 61, 66, 67, 68, 72, 72, 75, 81, 81, 82, 83, 84, 85, 85, 85, 86, 87, 87, 87, 87, 88, 88, 89, 89, 90, 90, 91, 91, 92, 93, 95, 95, 96, 97].
The target value was 85 at index 80
HW Part 2: This time instead of utilizing binary search to do it I want you to use linear search to get to the same value and I want you to output the number of iterations it took to get there. Aswell as a congrats message upon getting there points will be awarded upon creativity and completion.
#Code in here
import random
import emoji
# function for binary search
def linearSearch(endNum, numList):
count = 0
for i in range(len(numList)):
count += 1
if numList[i] == endNum:
return i, count
# create list of 100 random numbers
numList = []
x = 0
while x<100:
num = random.randint(0,100)
numList.append(num)
x += 1
print(f"This is the list in question with a length of {len(numList)}: {numList}.")
# pick random number to find using binary search
endNumIndex = random.randint(0,99)
endNum = numList[endNumIndex]
# call function and print result
output, endCount = linearSearch(endNum, numList)
print("Congratulations" + emoji.emojize(":partying_face:") + emoji.emojize(":party_popper:") + emoji.emojize(":double_exclamation_mark:") + " The target number was found " + emoji.emojize(":thumbs_up:") + emoji.emojize(":double_exclamation_mark:"))
print(f"The target number was {endNum} at index {output}. It took {endCount} iterations to get the target number.")
This is the list in question with a length of 100: [29, 87, 87, 81, 100, 84, 87, 41, 9, 80, 16, 62, 34, 39, 26, 83, 27, 16, 3, 85, 36, 62, 84, 90, 32, 2, 22, 83, 9, 37, 74, 91, 80, 32, 50, 1, 14, 13, 29, 25, 70, 57, 53, 35, 86, 98, 37, 49, 66, 31, 20, 80, 89, 14, 45, 0, 51, 33, 19, 69, 91, 59, 38, 81, 77, 40, 45, 7, 12, 58, 52, 47, 89, 7, 100, 100, 56, 60, 84, 66, 72, 91, 48, 25, 48, 79, 90, 7, 96, 0, 85, 30, 7, 37, 71, 63, 38, 61, 41, 64].
Congratulations🥳🎉‼️ The target number was found 👍‼️
The target number was 29 at index 0. It took 1 iterations to get the target number.
# Extra Credit Codeforces
import random
# Create random array of 7 numbers from 0 to 10 and pick a k (number of operations) value from 1 to 10
numList = []
x = 0
while x<7:
num = random.randint(0,10)
numList.append(num)
x += 1
sortNumList = sorted(numList)
print(f"The sorted number list is {sortNumList}")
k = random.randint(1, 10)
print("The k is " + str(k))
# Function to find max possible median
def maxMedian(sortNumList, k):
# List is already odd, so no need to account for even number of integers and find the middle
# odd. ex: 1, 2, 3, 4, 5. Median is at index 2
y = 0
while y < k:
medianIndex = int((len(sortNumList) - 1)/2)
sortNumList[medianIndex] += 1
sortNumList.sort()
print(f"The list after {y+1} operation(s): {sortNumList}")
y += 1
print(f"The highest possible median is {sortNumList[medianIndex]}")
maxMedian(sortNumList, k)
The sorted number list is [0, 1, 2, 2, 2, 4, 7]
The k is 7
The list after 1 operation(s): [0, 1, 2, 2, 3, 4, 7]
The list after 2 operation(s): [0, 1, 2, 3, 3, 4, 7]
The list after 3 operation(s): [0, 1, 2, 3, 4, 4, 7]
The list after 4 operation(s): [0, 1, 2, 4, 4, 4, 7]
The list after 5 operation(s): [0, 1, 2, 4, 4, 5, 7]
The list after 6 operation(s): [0, 1, 2, 4, 5, 5, 7]
The list after 7 operation(s): [0, 1, 2, 5, 5, 5, 7]
The highest possible median is 5