Binary Search

def search(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    high = len(nums)-1
    low = 0
    firstRes = -1
    # 要 low <= high 夾擠夾到, 若只有 < 出錯高達95%
    while low <= high:
        # mid = (high + low) // 2 : not recommended (overflow issue)

        mid = low + (high-low)//2
        if nums[mid] == target:
            firstRes = mid
            high = mid -1

        elif target < nums[mid]:
            high = mid - 1
        else:
            low = mid + 1
    """
    memo = []
    while 0 <= firstRes < len(nums) and target == nums[firstRes]:
        memo.append(firstRes)
    return memo
    """
    return firstRes
search([-1,0,3,5,9,12], 9)