Binary Search

# Time complexity: O(log n)
# Space complexity: O(1)
def searchInsert(nums: List[int], target: int) -> int:
    start, end = 0, len(nums) - 1

    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

    # Start will be equivalent to mid or mid + 1 for insert position
    return start

# Time complexity: O(log(m * n))
# Space complexity: O(1)
def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    # Binary search to find row containing target
    start, end = 0, len(matrix) - 1
    inRow = -1
    while start <= end:
        mid = (start + end) // 2
        if matrix[mid][0] > target:
            end = mid - 1
        elif matrix[mid][-1] < target:
            start = mid + 1
        else:
            inRow = mid
            break
    if inRow == -1:
        return False

    # Binary search to find target in row
    start, end = 0, len(matrix[0])
    while start <= end:
        mid = (start + end) // 2
        if matrix[inRow][mid] == target:
            return True
        elif matrix[inRow][mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return False

# Time complexity: O(log n)
# Space complexity: O(1)
def findPeakElement(nums: List[int]) -> int:
    # Check ends of list now to prevent boundary checks later
    if len(nums) == 1 or nums[0] > nums[1]:
        return 0
    if nums[-1] > nums[-2]:
        return len(nums) - 1

    start, end = 1, len(nums) - 2
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
            return mid
        # A peak is guaranteed to exist on the side that is higher,
        #   either as a normal peak with two neighbors, or the end of the list.
        elif nums[mid] < nums[mid - 1]:
            end = mid - 1
        else:
            start = mid + 1

# Time complexity: O(log n)
# Space complexity: O(1)
def search(nums: List[int], target: int) -> int:
    start, end = 0, len(nums) - 1

    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            return mid

        # Logic: at most only one side is rotated
        # If left side is not rotated
        if nums[start] <= nums[mid]:  # Must use <= in case start == mid
            if nums[start] <= target <= nums[mid]:
                end = mid - 1
            else:
                start = mid + 1
        # Else right side is not rotated
        else:
            if nums[mid] <= target <= nums[end]:
                start = mid + 1
            else:
                end = mid - 1

    return -1

# Time complexity: O(log n)
# Space complexity: O(1)
def searchRange(nums: List[int], target: int) -> List[int]:
    answer = [-1, -1]

    # Two binary searches to find first and last index
    # Instead of stopping search when target found, keeping going

    start, end = 0, len(nums) - 1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            answer[0] = mid

        if nums[mid] >= target:
            end = mid - 1
        else:
            start = mid + 1

    start, end = 0, len(nums) - 1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            answer[1] = mid

        if nums[mid] <= target:
            start = mid + 1
        else:
            end = mid - 1

    return answer

# Time complexity: O(log n)
# Space complexity: O(1)
def findMin(nums: List[int]) -> int:
    start, end = 0, len(nums) - 1

    while start < end:
        mid = (start + end) // 2
        # If right side is rotated, answer is in right side
        if nums[mid] > nums[end]:
            # nums[mid] cannot be the answer, so mid is safe to skip
            start = mid + 1
        else:
            end = mid
    return nums[start]

    # The following conditional does not work. If the left side is rotated,
    #   it is possible that nums[mid] is the answer

    # if nums[start] > nums[mid]:
    #     end = mid - 1
    # else:
    #     start = mid