BS

# binary search with O(logn)
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        s, end = 0, len(nums)-1
        while s<=end:
            mid = s + int((end-s)/2)
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                end = mid-1
            else:
                s = mid+1
        return -1