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

class Solution:
    
    def search(self, nums: List[int], target: int) -> int:
        return self.searchHelper(nums, 0, len(nums) - 1, target)
        
    def searchHelper(nums, start, end, target):
        if start > end:
            return -1
        mid = (start + end) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return self.searchHelper(nums, mid + 1, end, target)
        else:
            return self.searchHelper(nums, start, mid - 1, target)
        
    def iterativeBinarySearch(nums, target):
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return -1

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

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

## [First Bad Version](https://leetcode.com/problems/first-bad-version/)

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        start, end = 1, n
        while start <= end:
            mid = (start + end) // 2
            if isBadVersion(mid):
                end = mid - 1
            else:
                start = mid + 1
        return start

## Misc

def printAllValues(nums):
    for n in nums:
        print(n)

def printAllValuesRecursive(nums):
    printAllValuesRecursiveHelper(nums, 0)
    
def printAllValuesRecursiveHelper(nums, currIndex):
    if currIndex >= len(nums):
        return
    print(nums[currIndex])
    printAllValuesRecursiveHelper(nums, currIndex + 1)

printAllValuesRecursive([1,2,3])

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

print(factorial(5)) // 5 * 4 * 3 * 2 * 1

//fib(n) = fib(n - 1) + fib(n - 2)
// 0, 1, 1, 2, 3, 5, 8, ...
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

def tabFib(n):
    fibs = [0, 1]
    for i in range(2, n + 1):
        fibs.append(fibs[i - 1] + fibs[i - 2])
    return fibs[n]