# Sprint 2 Module Project 4
## fibonacciSimpleSum2

def fibonacciSimpleSum2(n):
    fibNumbers = [0, 1]
    while fibNumbers[-1] < n:
        fibNumbers.append(fibNumbers[-1] + fibNumbers[-2])
    left = 0
    right = len(fibNumbers) - 1
    while left < right:
        num = fibNumbers[left] + fibNumbers[right]
        if num == n:
            return True
        elif num < n:
            left += 1
        else:
            right -= 1
    return False

## csBinarySearch

def csBinarySearch(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

## csSearchRotatedSortedArray

def csSearchRotatedSortedArray(nums, target):
    if len(nums) == 0:
            return -1
    low = 0
    high = 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