"""

1. Compare target with the middle element.

2. If target matches with the middle element, we return the mid index.

3. Else If target is greater than the mid element, then target can only lie in right half subarray, so we move the right, after the mid element. So we recur for the right half.

4. Else (target is smaller than mid) recur for the left half, move the high to the left.

5. If search to the end and we couldn't find the terget, return -1.
   """
   class Solution:
   def search(self, nums: List[int], target: int) -> int:
   low = 0
   high = len(nums)-1
   mid = 0

    while low <= high:
        mid = (low + high) // 2
        if target == nums[mid]:
            return mid
        elif target < nums[mid]:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1