1. What is the range of values in nums?
2. What is the possible size of nums?
3. Can there be duplicates in nums? If so, which index do we return (any or left-most or right-most)?

1. This is straightforward since we're obviously implementing binary search.
2. Another option is precomputing solutions to speed up to constant time for future calls but the title is asking for binary search so let's go with that.

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        left = 0
        right = len(nums)-1
        
        while left <= right:
            # normal middle is (left + right)/2
            middle = left + int((right - left)/2)
            
            if nums[middle] == target:
                return middle
            elif nums[middle] > target:
                right = middle - 1
            else:
                left = middle + 1
                
        return -1

1. Target is in nums
2. Target is not in nums
3. Empty nums
4. Single nums and test target in/out of nums

O(log n) for speed due to binary search and O(1) for space

1. Implementing binary search can get tricky. Depending on how we set right's initial value, we might have to use left < right and assign right = middle instead of the solution above where we use left <= right and right = middle -1. An easy way to remember is what do we want to do if the list is 1 element. If the right is needs to be included, we want left <= right to get into the while loop. Then, right becomes middle + 1 since we already checked the right = middle case.
2. Things could get trickier if we want left most target or right most but luckily not needed here.
3. In python, it is easy to forget that you can't add a float to an int and (right-left)/2 gives a float. Thus, the casting. Note that we likely don't have to do the middle trick here in Python since integer overflow is tied to memory instead of a hard-coded value.