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 )
# Creating a list with some initial elements
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# Inserting the string " maybe" at index 5 (the 6th position in the list)
lst.insert(5, " maybe")
# Printing the modified list to the console
print(lst)
[1, 2, 3, 4, 5, ' maybe', 6, 7, 8, 9]
Remove function
- The remove functions allows you to remove specific items at a specific position on the list
Pseudocode example
- REMOVE aList, pos
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']
hi
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]
# Assuming the first number in the list is the smallest initially
min_num = nums[0]
# Iterating through the list to find the minimum number
for num in nums:
if num < min_num:
min_num = num
print(min_num, "is the lowest number in the nums list")
28 is the lowest number in the nums list
# Assuming this is your animals list
animals = ["cats", "dogs", "cats", "dogs", "dogs", "cats", "cats"]
# Initializing counters for cats and dogs
cats_count = 0
dogs_count = 0
# Iterating through the list to count cats and dogs
for animal in animals:
if animal == "cats":
cats_count += 1
elif animal == "dogs":
dogs_count += 1
print("Total cats:", cats_count)
print("Total dogs:", dogs_count)
Total cats: 4
Total dogs: 3
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 = 3
result = binarySearch(sorted_list, 5)
print(result)
1
#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]
target = 3
result = linear_search(target, sorted_list)
print(result)
1
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
import random
from typing import ItemsView
def linear_search(items, target):
"""
Perform linear search on items for the target value.
Return the index if found, otherwise return -1.
"""
for i, item in enumerate(list):
if item == target:
return i
return -1
# Create a list with given elements
list = ["eggs", "milk", "butter", "cake"]
# Randomly choose an item from the list
chosen_item = random.choice(list)
# Print the chosen item
print("Chosen item:", chosen_item)
# Call the linear_search function to find the index of the chosen item
index = linear_search(list, chosen_item)
# Print the index of the chosen item
print("Index of", chosen_item, "is:", index)
Chosen item: butter
Index of butter 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
import random
# Generate a random number between 1 and 100
target_number = random.randint(1, 100)
# Define the sorted list of numbers
numbers = list(range(1, 101))
# Initialize variables for binary search
low = 0
high = len(numbers) - 1
tries = 0
# Binary search to guess the number
while low <= high:
mid = (low + high) // 2
guess = numbers[mid]
tries += 1
print(f"Try {tries}: The guess is {guess}")
if guess < target_number:
print("The number is higher.")
low = mid + 1
elif guess > target_number:
print("The number is lower.")
high = mid - 1
else:
print(f"Congratulations! The number is {guess} and it took {tries} tries to guess it.")
break
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In[30], line 7
4 target_number = random.randint(1, 100)
6 # Define the sorted list of numbers
----> 7 numbers = list(range(1, 101))
9 # Initialize variables for binary search
10 low = 0
TypeError: 'list' object is not callable
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.
import random
# Generate a random number between 1 and 100
target_number = random.randint(1, 100)
# Print welcoming message
print("Welcome to the Guessing Game!")
print("I have chosen a number between 1 and 100.")
# Initialize the number of tries
tries = 0
# Linear search to guess the number
for guess in range(1, 101):
tries += 1
print(f"Try {tries}: Guessing {guess}...")
if guess < target_number:
print("The number is higher.")
elif guess > target_number:
print("The number is lower.")
else:
print(f"\nCongratulations! You've found the number {guess}.")
print(f"It took you {tries} tries to guess it.")
print("🎉🥳🎊 You're a star! 🌟✨💫")
break
Welcome to the Guessing Game!
I have chosen a number between 1 and 100.
Try 1: Guessing 1...
The number is higher.
Try 2: Guessing 2...
The number is higher.
Try 3: Guessing 3...
The number is higher.
Try 4: Guessing 4...
The number is higher.
Try 5: Guessing 5...
The number is higher.
Try 6: Guessing 6...
The number is higher.
Try 7: Guessing 7...
The number is higher.
Try 8: Guessing 8...
The number is higher.
Try 9: Guessing 9...
The number is higher.
Try 10: Guessing 10...
The number is higher.
Try 11: Guessing 11...
The number is higher.
Try 12: Guessing 12...
The number is higher.
Try 13: Guessing 13...
The number is higher.
Try 14: Guessing 14...
The number is higher.
Try 15: Guessing 15...
The number is higher.
Try 16: Guessing 16...
The number is higher.
Try 17: Guessing 17...
The number is higher.
Try 18: Guessing 18...
The number is higher.
Try 19: Guessing 19...
The number is higher.
Try 20: Guessing 20...
The number is higher.
Try 21: Guessing 21...
The number is higher.
Try 22: Guessing 22...
The number is higher.
Try 23: Guessing 23...
The number is higher.
Try 24: Guessing 24...
The number is higher.
Try 25: Guessing 25...
The number is higher.
Try 26: Guessing 26...
The number is higher.
Try 27: Guessing 27...
The number is higher.
Try 28: Guessing 28...
The number is higher.
Try 29: Guessing 29...
The number is higher.
Try 30: Guessing 30...
The number is higher.
Try 31: Guessing 31...
The number is higher.
Try 32: Guessing 32...
The number is higher.
Try 33: Guessing 33...
The number is higher.
Try 34: Guessing 34...
The number is higher.
Try 35: Guessing 35...
The number is higher.
Try 36: Guessing 36...
The number is higher.
Try 37: Guessing 37...
The number is higher.
Try 38: Guessing 38...
The number is higher.
Try 39: Guessing 39...
The number is higher.
Try 40: Guessing 40...
The number is higher.
Try 41: Guessing 41...
The number is higher.
Try 42: Guessing 42...
The number is higher.
Try 43: Guessing 43...
The number is higher.
Try 44: Guessing 44...
The number is higher.
Try 45: Guessing 45...
The number is higher.
Try 46: Guessing 46...
The number is higher.
Try 47: Guessing 47...
The number is higher.
Try 48: Guessing 48...
The number is higher.
Try 49: Guessing 49...
The number is higher.
Try 50: Guessing 50...
The number is higher.
Try 51: Guessing 51...
The number is higher.
Try 52: Guessing 52...
The number is higher.
Try 53: Guessing 53...
The number is higher.
Try 54: Guessing 54...
The number is higher.
Try 55: Guessing 55...
The number is higher.
Try 56: Guessing 56...
The number is higher.
Try 57: Guessing 57...
The number is higher.
Try 58: Guessing 58...
The number is higher.
Try 59: Guessing 59...
The number is higher.
Try 60: Guessing 60...
The number is higher.
Try 61: Guessing 61...
The number is higher.
Try 62: Guessing 62...
The number is higher.
Try 63: Guessing 63...
The number is higher.
Try 64: Guessing 64...
The number is higher.
Try 65: Guessing 65...
The number is higher.
Try 66: Guessing 66...
The number is higher.
Try 67: Guessing 67...
The number is higher.
Try 68: Guessing 68...
The number is higher.
Try 69: Guessing 69...
The number is higher.
Try 70: Guessing 70...
The number is higher.
Try 71: Guessing 71...
The number is higher.
Try 72: Guessing 72...
The number is higher.
Try 73: Guessing 73...
The number is higher.
Try 74: Guessing 74...
Congratulations! You've found the number 74.
It took you 74 tries to guess it.
🎉🥳🎊 You're a star! 🌟✨💫