# CSPT21 Lecture 8
## [Binary Search](https://leetcode.com/problems/binary-search/)

class Solution:
    """
    
    nums = [-1,0,3,5,9,((12*))], target = 13
    min = 6
    max = 5
    mid = 5
    """
    def search(self, nums: List[int], target: int) -> int:
        min, max = 0, len(nums) - 1
        while min <= max:
            mid = (min + max) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                min = mid + 1
            else:
                max = mid - 1
        return -1

## [Guess Number](https://leetcode.com/problems/guess-number-higher-or-lower/)

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:

class Solution:
    """
    n = 10, guess = 1
    
    min = 1
    max = 1
    mid = 1
    res = 0
    """
    def guessNumber(self, n: int) -> int:
        min, max = 1, n
        while min <= max:
            mid = (min + max) // 2
            res = guess(mid)
            if res == 0:
                return mid
            elif res == -1:
                max = mid - 1
            else:
                min = mid + 1
        return -1

## [Fibonacci](https://leetcode.com/problems/fibonacci-number/)

class Solution:
    # memoizing = remember the old values you've computed so you don't recompute them again
    def fib(self, n: int) -> int:
        computedValues = {0: 0, 1: 1}
        return self.memoizedFib(n, computedValues)
        
    def memoizedFib(self, n, computedValues):
        if n in computedValues:
            return computedValues[n]
        computedValues[n] = self.memoizedFib(n - 1, computedValues) + self.memoizedFib(n - 2, computedValues)
        return computedValues[n]
    
    def dumbFib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)

## Other

def memoizedFactorial(n):
    computedValues = {0: 1, 1: 1}
    return memoizedFactorialHelper(n, computedValues)

def memoizedFactorialHelper(n, computedValues):
    if n in computedValues:
        return computedValues[n]
    computedValues[n] = n * memoizedFactorialHelper(n - 1, computedValues)
    return computedValues[n]

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print(memoizedFactorial(3)) # 6
print(memoizedFactorial(4)) # 24
print(memoizedFactorial(5)) # 120