class Solution:
	def search(self, nums: List[int], target: int) -> int:
		# The boundary is inclusive which determines the while condition
		head, tail = 0, len(nums) - 1
		# since the boundary is inclusive on the two ends of the nums array
		# we should search even when head == tail and we should just check 
		# that particular value
		while head <= tail:
			# we use floor division to make sure mid is an integer otherwise
			# it cannot be used to index
			# and using floor division will always result in a smaller value
			# towards head so we don't want to stop search when head < tail 
			mid = (head + tail) // 2
			# this is the part I love about this approach
			# we can return the result right away if it is equal to the target as
			# 1: we don't have to go through all search space
			# 2: we can safely eliminate mid point in the next search
			if nums[mid] == target:
				return mid
			# if target is larger than nums[mid], it indicates the result sits
			# on the left of mid, and otherwise the result sits on the right
			if nums[mid] < target:
				# since we are sure nums[mid] is not the result, we don't have
				# to check nums[mid] again and we could move head to mid + 1
				# otherwise, we move tail to mid - 1
				head = mid + 1
			else:
				tail = mid - 1
		# we are sure no results are found since all space are searched
		return -1

class Solution:
	# we are using binary search because the search space is sorted and must be
	# from [1, x]
    def mySqrt(self, x: int) -> int:
        if x < 2: return x
        # The search space is [0, x//2] since it is to find the square root
        head, tail = 0, x // 2
	
        while head <= tail:
            mid = (head + tail) // 2
            temp = mid * mid
            if temp == x:
                return mid
            elif temp < x:
                head = mid + 1
            else:
                tail = mid - 1
        
        if mid * mid > x:
            return mid - 1
        else:
            return mid

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        head = 0
        tail = len(nums) - 1

        while head <= tail:
            mid = (head + tail) // 2
            if nums[mid] == target:
                return mid
            if nums[head] <= nums[mid]:
                if nums[head] <= target <= nums[mid]:
                    tail = mid - 1
                else:
                    head = mid + 1
            else:
                if nums[mid] <= target <= nums[tail]:
                    head = mid + 1
                else:
                    tail = mid - 1
        
        return -1

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        m, n = len(nums1), len(nums2)
        # the search space is the length of the array unlike the index in above questions, this is important since the array is 0-indexed.
        head, tail = 0, m
        while head <= tail:
	        # this the length we attempt to grap from nums1
            mid1 = (head + tail) // 2
			# this is the length we attempt to grap from nums2, it is (m + n + 1)//2 - mid1 so mid2 will not be negative
			# when mid1 increases and equal to m, (m + n)//2 - m could be negative when n < m and (m + n) is odd, thus (m + n + 1) ensure mid2 won't be negative
            mid2 = (m + n + 1) // 2 - mid1
			# if the length is 0 for either nums1 or nums2, the value on the left should be infinite negative since there is no value
            maxLeft1 = float("-inf") if mid1 == 0 else nums1[mid1 - 1]
            maxLeft2 = float("-inf") if mid2 == 0 else nums2[mid2 - 1]
			# likewise, if entire elements are grapped, the element on the right is infinite positive
            minRight1 = float("inf") if mid1 == m else nums1[mid1]
            minRight2 = float("inf") if mid2 == n else nums2[mid2]
			# since we get mid2 from mid1 and the total length, the mid1 and mid2 should always slice the entire elements into half and we only need check if the elements to the left of mid1 and mid2 are less than those on the other side.
            if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
	            # if so, we calculate the median given the total size
                if (m + n) % 2 == 0:
	                # if it is even, we need the value on the left and right of mid since it requires two value
                    return (min(minRight1, minRight2) + max(maxLeft1, maxLeft2)) / 2
                else:
	                # otherwise, we only need the max of maxLeft1 and maxLeft2 
                    return max(maxLeft1, maxLeft2)
            else:
	            # if the ending condition doesn't meet, we should adjust the search space to contain less elements from nums1 since the left value of mid1, maxLeft1, is larger than the right value of mid2, minRight2
                if maxLeft1 > minRight2:
                    tail = mid1 - 1
                else:
                    head = mid1 + 1

class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
	    # set the two end of search space
        head, tail = 1, max(ribbons)
		# check how many ribbons can be made
        def helper(cut):
            count = 0
            for ribbon in ribbons:
                count += ribbon // cut
            return count

        while head <= tail:
            mid = (head + tail) // 2
            # if we get more than k rippons, we could try a larger value
            if helper(mid) >= k:
                head = mid + 1
            else:
                tail = mid - 1
        # here we return tail instead of mid
        # In one word, the search space will be between two values at the end 
        # suppose head = 4 and tail = 5, so mid = 4 due to floor division, then we have two scenarios 4 is the answer and 4 is not the answer. But no matter what, we will make head = mid + 1 = 5 (since 4 will def generate k or more than k rippons, otherwise the head won't be 4 at the last round). 
        # When head = 5, the mid = 5
	        #if 5 is not the answer, tail will become mid - 1 = 4 and we finish search
	        #if 5 is the answer, head = mid + 1 = 6 > tail = 5, we also finish search
	    # thus we should return tail as the result   
        return tail