'''
keys: pay attention to the left and right update, also the l <= r
using = is because: In the case of a list with length of 1, 
like [5] for example, it will fail because from the very beginning 
both l and r are both 0 so the while condition is never satisfied
Solutions:
Similar: 
T:
S:
'''
from typing import List


class Solution:
    # T: O(logN); S: O(1)
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r-l)//2
            if target == nums[mid]:
                return mid
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return -1