# CSPT25 Lecture 8
## Guess Number

# 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:
    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

## Binary Search

class Solution:
    """
    nums = [-1,0,3,5,9], target = 9
    output = 4
    
    nums = [-1,0,3,5,9], target = 2
    output = -1
    
    nums = [1], target = 1
    output = 0
    
    nums = [1], target = -2
    output = -1
    
    nums = [-1,(0*),[3],5,9], target = 2
    mid = 1 + 1 // 2 = 1
    """
    def search(self, nums: List[int], target: int) -> int:
        return self.searchHelper(nums, target, 0, len(nums) - 1)
        
    def searchHelper(self, nums, target, min, max):
        if min > max:
            return -1
        mid = (min + max) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return self.searchHelper(nums, target, mid + 1, max)
        else:
            return self.searchHelper(nums, target, min, mid - 1)
    
    def searchIterative(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

## Fibonacci Number

class Solution:
    def fib(self, n: int) -> int:
        computedValues = {1: 1, 0: 0}
        return self.fibHelper(n, computedValues)
    
    def fibHelper(self, n, computedValues):
        if n in computedValues:
            return computedValues[n]
        computedValues[n] = self.fibHelper(n - 1, computedValues) + self.fibHelper(n - 2, computedValues)
        return computedValues[n]
    
    def naiveFib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)