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

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

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

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)