# Sprint 2 Module Project 4
## fibonacciSimpleSum2

def fibonacciSimpleSum2(n):
    fibs = [0, 1]
    while fibs[-1] < n:
        fibs.append(fibs[-1] + fibs[-2])
    for num in fibs:
        if binarySearch(fibs, n - num):
            return True
    return False
    
def binarySearch(nums, target):
    start, end = 0, len(nums) - 1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            return True
        if nums[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return False

## csBinarySearch

def csBinarySearch(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

## csSearchRotatedSortedArray

def csSearchRotatedSortedArray(nums, target):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[low] <= nums[mid]:
            if nums[low] <= target and target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if nums[mid] < target and target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    if nums[low] == target:
        return low
    else:
        return -1