3.9/3.11- Deveoping Algorithms/Binary Search

  • Algorithms
  • You can make a grade callulator based on a certain persecntage and arithmetic
  • When collaborating or working on group projects, two people might come up with two different ways to solve a problem, and that happens a lot.
  • know that same goal can be achieved in many ways (the possibilities are endless)
  • make notes in you code! (explain how it works to others or you future self)
  • Boolean statements can be put into nested conditionals to cause a chain of asking wheter an item is true or false with a lot of questions.
  • Outlining an algorithm is very important to know how to organize your code.
  • Iteration is like a loop
  • Existing Algorithm:
    • determining min or max of two or more numbers
    • computing the sum or average
    • identifying if an integer is even or odd
  • Binary Search: To divide a serach interval in half multiple times until something stops it

Hacks

Hack 1

  1. It is important to know that algorithms that look different can do the same thing and algorithms that look the same might have differnt results for multiple reason. If you are working with a team you have to understand what their code is saying so you can use it with them. Also it allows you to make different types of code and understand it better making you an even better programmer. 
isFriday = True
isThurday = False

#If Statements
if isFriday == True:
    print("Go to Canes")
else:
    print("It's not Friday and that sucks")

if isThurday == True:
    print("Go to practice")

Go to Canes

isFriday = False
isThursday = True
# Setting Var
doHomework = isThursday or not(isFriday)
# If statements
if doHomework == False:
    print("Don't do Homework")
else:
    print("Do Homework")

Do Homework

Hacks 2

Flowchart

Natural lang

  • Start
  • Are you old enought to drink
  • if not wait a year
  • do you have money
  • if not you're poor
  • if so you get beer
age = 17
money = 4

#When they are under age they wait a year until they are over
while age <= 20:
    age = age + 1
    print(age)
if age >= 21:
    if money >= 3.99:
        print("Here is your Drink")
        #if they don't have enough money they will say they are poor
    else:
        print("im poor")

18
19
20
21
Here is your Drink

Hack 3 

import random

#sets variables for the game
num_guesses = 0
user_guess = -1
upper_bound = 100
lower_bound = 0

#generates a random number
number = random.randint(0,100)

# print(number)     #for testing purposes

print(f"I'm thinking of a number between 1 and 100.")

#Write a function that gets a guess from the user using input()
def guess():
    #add something here
    num = input("What is the number you are thinking of?")
    return num #add something here 

#Change the print statements to give feedback on whether the player guessed too high or too low
def search(number, guess):
    global lower_bound, upper_bound
    if int(guess) < int(number):
        print("You guessed too low") #change this
        lower_bound = guess
        return lower_bound, upper_bound
    elif int(guess) > int(number):
        print("You guessed too high") #change this
        upper_bound = guess
        return lower_bound, upper_bound
    else:
        upper_bound, lower_bound = guess, guess
        return lower_bound, upper_bound

while user_guess != number:
    user_guess = guess()
    num_guesses += 1
    print(f"You guessed {user_guess}.")
    lower_bound, upper_bound = search(number, user_guess)
    if int(upper_bound) == int(number):
        break
    else:
        print(f"Guess a number between {lower_bound} and {upper_bound}.")

print(f"You guessed the number in {num_guesses} guesses!")

I'm thinking of a number between 1 and 100.
You guessed 50.
You guessed too high
Guess a number between 0 and 50.
You guessed 29.
You guessed too low
Guess a number between 29 and 50.
You guessed 33.
You guessed too low
Guess a number between 33 and 50.
You guessed 40.
You guessed too high
Guess a number between 33 and 40.
You guessed 37.
You guessed too high
Guess a number between 33 and 37.
You guessed 35.
You guessed too high
Guess a number between 33 and 35.
You guessed 34.
You guessed the number in 7 guesses!

#

Flowchart

Hack 4 

index = [12, 14, 43, 57, 79, 80, 99]

mid = int(len(index) / 2) 
print(mid)
print(index[mid])

index = [92, 43, 74, 66, 30, 12, 1]

mid = int(len(index) / 2) 
print(mid)
print(index[mid])

index = [7, 13, 96, 111, 33, 84, 60]

mid = int(len(index) / 2) 
print(mid)
print(index[mid])

Flowchart Flowchart Flowchart

  1. Set 1: 80, Set 2: 74, Set 3: 96
  1. C is unsorted therefore it is correct.

Vocab

  • Existing Algorithm: determining min or max of two or more numbers,computing the sum or average, identifying if an integer is even or odd
  • Binary Search: To divide a serach interval in half multiple times until something stops it
  • Boolean statments: Put into nested conditionals to cause a chain of asking wheter an item is true or false with a lot of questions.
def binary_search(arr, target):
  
  start = 0
  end = len(arr) - 1
  
  
  while start <= end:
    
    mid = (start + end) // 2
    
    
    if target > arr[mid]:
      start = mid + 1
    
    elif target < arr[mid]:
      end = mid - 1
    
    else:
      return mid
      

  return -1

SkyBlue = True
if SkyBlue == True: 
    print("The Sky is Blue")

The Sky is Blue