# CSPT17 Lecture 8

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

def search(self, nums: List[int], target: int) -> int:
    min, max = 0, len(nums) - 1
    while min <= max:
        mid = int((min + max) / 2)
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            min = mid + 1
        else:
            max = mid - 1
    return -1

# Recursive solution
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 = int((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)

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

"""
Plan
Use binary search to guess the correct number, use api provided to determine
whether to search higher/lower range
"""
def guessNumber(self, n: int) -> int:
    min, max = 1, n
    while min <= max:
        mid = int((min + max) / 2)
        res = guess(mid)
        if res == 0:
            return mid
        elif res == -1:
            max = mid - 1
        else:
            min = mid + 1
    return -1

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

"""
Understand
n = 5, bad = 3

n = 1, bad = 1

n = 5, bad = 5

Plan
Use binary search.

If middle element is bad, then that element is either
the first bad version or it's somewhere on the left side. Traverse left

If middle element is good, then the first bad element is on the right side. Traverse right

If min > max, then the first bad element is min
"""

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