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: 
# Inserting items to a specific list, remember python is 0 based on the items!!
lst.insert(5, " maybe")
print(lst)

['hi', 'no', ' maybe']

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])

['no', ' maybe']
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

35
this number is the lowest number in the nums list

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:

  1. First Step: You open the book in the middle.
  2. Second Step: Is the name before or after the middle? You eliminate half of the remaining names.
  3. Repeat: Keep dividing until you find the name or run out of names to check.
  4. 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

#code here
food = ["eggs", "milk", "butter", "cake"]
target = random.randint(0,len(food))
for item in range (len(food)):
    if item == target:
        print(food[item], item)

milk 1

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
import math

my_sorted_list = []
for i in range(100):
    new_number = random.randint(1, 1000)
    
    while new_number in my_sorted_list:
        new_number = random.randint(1, 1000)
    
    my_sorted_list.append(new_number)

my_sorted_list.sort() 

num_attempts = 0 

def binary_search(target, start, end):
    global num_attempts
    
    if start > end:
        return "Not found"

    middle = math.floor((start + end) / 2)

    if my_sorted_list[middle] == target:
        return f"Congratulations, you found {target} at index {middle} after {num_attempts} attempts."
    
    if my_sorted_list[middle] > target:
        num_attempts += 1
        print(f"Attempt {num_attempts}: {my_sorted_list[middle]}")
        return binary_search(target, start, middle - 1)
    
    if my_sorted_list[middle] < target:
        num_attempts += 1
        print(f"Attempt {num_attempts}: {my_sorted_list[middle]}")
        return binary_search(target, middle + 1, end)

my_target = my_sorted_list[random.randint(0, len(my_sorted_list) - 1)]
print(my_sorted_list)
result = binary_search(my_target, 0, len(my_sorted_list) - 1)
print(result)


[13, 29, 30, 41, 47, 75, 108, 115, 129, 130, 142, 144, 153, 206, 214, 247, 256, 264, 271, 272, 301, 309, 328, 329, 340, 353, 369, 374, 378, 379, 383, 390, 401, 408, 409, 411, 427, 430, 436, 458, 468, 497, 498, 509, 524, 529, 550, 553, 560, 567, 569, 578, 588, 593, 597, 603, 614, 621, 634, 657, 666, 673, 685, 701, 706, 718, 719, 720, 725, 732, 733, 750, 759, 760, 784, 793, 797, 827, 832, 836, 839, 842, 849, 852, 883, 890, 896, 898, 918, 926, 927, 936, 937, 951, 954, 960, 976, 977, 983, 999]
Attempt 1: 567
Attempt 2: 784
Attempt 3: 673
Attempt 4: 603
Attempt 5: 588
Congratulations, you found 593 at index 53 after 5 attempts.

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

my_sorted_list = []
for i in range(100):
    new_number = random.randint(1, 1000)
    
    while new_number in my_sorted_list:
        new_number = random.randint(1, 1000)
    
    my_sorted_list.append(new_number)

my_sorted_list.sort()

def linear_search(target):
    num_attempts = 0
    
    for i in my_sorted_list:
        num_attempts += 1
        
        if i == target:
            print(f"Congratulations! You found {target} at index {my_sorted_list.index(i)} after {num_attempts} attempts.")
            return 
        else:
            print(f"Attempt {num_attempts}: {i}")
my_target = my_sorted_list[random.randint(0, len(my_sorted_list) - 1)]
result = linear_search(my_target)


Attempt 1: 11
Attempt 2: 25
Attempt 3: 29
Attempt 4: 38
Attempt 5: 42
Attempt 6: 55
Attempt 7: 91
Attempt 8: 93
Attempt 9: 107
Attempt 10: 126
Attempt 11: 128
Attempt 12: 134
Attempt 13: 149
Attempt 14: 157
Attempt 15: 163
Attempt 16: 183
Attempt 17: 190
Attempt 18: 196
Attempt 19: 207
Attempt 20: 220
Attempt 21: 229
Attempt 22: 243
Attempt 23: 249
Attempt 24: 255
Attempt 25: 264
Attempt 26: 271
Attempt 27: 282
Attempt 28: 284
Attempt 29: 299
Attempt 30: 301
Attempt 31: 302
Attempt 32: 304
Attempt 33: 315
Attempt 34: 317
Attempt 35: 320
Attempt 36: 326
Attempt 37: 337
Attempt 38: 338
Attempt 39: 346
Attempt 40: 347
Attempt 41: 370
Attempt 42: 371
Attempt 43: 378
Attempt 44: 383
Attempt 45: 387
Attempt 46: 402
Congratulations! You found 407 at index 46 after 47 attempts.