# burte force
#  - time: O(n)

# binary search - 写法1 
#  - time: O(logn)
#  - space: O(1)
	def search(self, nums: List[int], target: int) -> int:
		l, r = 0, len(nums) - 1
		while l <= r:
			m = (l + r) // 2
			if nums[m] == target:
				return m

			# the right portion is sorted
			if nums[m] < nums[r]: # e.g., [10, 11, 7, 8, 9]
				if target > nums[r] or target < nums[m]:
					r = m - 1
				else:
					l = m + 1
			else: # the left portion is sorted, e.g., [11, 12, 13, 14, 10]
				if target > nums[m] or target < nums[l]:
					l = m + 1
				else:
					r = m - 1
		return -1
  
# binary search - 写法2  
#  - time: O(logn)
#  - space: O(1)
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m

            if nums[l] <= nums[m]:
                # the left portion is sorted, e.g., [11, 12, 13, 14, 10]. 
                # Must use <=, because we have the case where m == l, e.g., [2,1]
                if target < nums[l] or target > nums[m]:
                    l = m + 1
                else:
                    r = m
            else:  # the right portion is sorted
                if target < nums[m] or target > nums[r]:
                    r = m - 1
                else:
                    l = m

        return -1

# binary search - 写法 1
#  - time: O(logn)
#  - space: O(1)  
	def searchRange(self, nums: List[int], target: int) -> List[int]:
		l, r = 0, len(nums) - 1
		while l <= r:
			m = (l + r) // 2
			if target < nums[m]:
				r = m - 1
			elif nums[m] < target:
				l = m + 1
			else:  # entering here means we found at least 1 target
				start, end = m, m
				pre_l, pre_r = l, r

				# to get min start
				l, r = pre_l, m
				while l <= r:  # l and r are the current searching ranges (inclusive)
					m = (l + r) // 2
					if nums[m] == target:
						r = m - 1
						start = min(start, m)
					elif nums[m] < target:
						l = m + 1

				# to get max end
				l, r = m, pre_r
				while l <= r:
					m = (l + r) // 2
					if nums[m] == target:
						l = m + 1
						end = max(end, m)
					elif nums[m] > target:
						r = m - 1

				return [start, end]  # if found at least 1 target, always return from here

		return [-1, -1]  # If not found the target, always return from here
  
# binary search - 写法2 - more elegent
#  - time: O(logn)
#  - space: O(1)  
	def searchRange(self, nums: List[int], target: int) -> List[int]:
		# if leftMost is true, find the leftmost index, otherwise find the rightmost index
		def binarySearch(leftMost):
			left, right = 0, len(nums) - 1,
			i = -1
			while left <= right:
				m = (left + right) // 2
				if target < nums[m]:
					right = m - 1
				elif nums[m] < target:
					left = m + 1
				else:
					i = m
					if leftMost:
						right = m - 1
					else:
						left = m + 1
			return i

		# time: O(2logn)
		l = binarySearch(True)
		r = binarySearch(False)
		return [l, r]

# binary search 
#  - time: O(log(m+n) (which reduces to O(log(m*n)))
#  - space: O(1)
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
		top, bottom = 0, len(matrix) - 1
		foundRow = False
		while top <= bottom:
			row = (top + bottom) // 2
			if matrix[row][0] <= target and matrix[row][-1] >= target:
				foundRow = True
				break
			elif matrix[row][0] > target:
				bottom = row - 1
			else:
				top = row + 1

		if not foundRow:
			return False

		row = (top + bottom) // 2
		left, right = 0, len(matrix[0]) - 1
		while left <= right:
			col = (left + right) // 2
			if matrix[row][col] == target:
				return True
			elif matrix[row][col] > target:
				right = col - 1
			else:
				left = col + 1
		return False

# binary search - more elegent
#  - time: O(logn)
#  - space: O(1)
	def findMin(self, nums: List[int]) -> int:
		cur_min = nums[0]  # record the min that we have seen
		l, r = 0, len(nums) - 1
		while l <= r:  # [l: r+1] are the current valid searching range, so we will search until empty range with recording the min that we have seen
			if nums[l] < nums[r]:  # meaning the array is sorted
				return min(cur_min, nums[l])

			m = (l + r) // 2
			if nums[l] <= nums[m]:  # meaning the left part [l: m+1] is the sorted portion. Must use <=, since l may be equal to m, e.g., [2, 1]
				cur_min = min(cur_min, nums[l])
				l = m + 1  # search the right part then
			else:  # nums[m] < nums[l] and nums[l] > nums[r]
				cur_min = min(cur_min, nums[m])
				r = m - 1  # search the left part then

		return cur_min

	def firstBadVersion(self, n: int) -> int:
		l, r = 1, n
		res = n
		while l <= r:
			m = (l + r) // 2
			if isBadVersion(m):
				res = min(res, m)
				r = m - 1
			else:
				l = m + 1
		return res

# Recursive Binary Search
# - time: O(logn)
# - space: O(1)
   def binary_search(self, l: int, r: int, nums: List[int], target: int) -> int:
        if l > r:
            return -1
        m = l + (r - l) // 2
        
        if nums[m] == target:
            return m
        if nums[m] < target:
            return self.binary_search(m + 1, r, nums, target)
        return self.binary_search(l, m - 1, nums, target)

    def search(self, nums: List[int], target: int) -> int:
        return self.binary_search(0, len(nums) - 1, nums, target)
      
# Iterative Binary Search
# - time: O(logn)
# - space: O(1)
 def search(self, nums: List[int], target: int) -> int:
		l, r = 0, len(nums) - 1
		while l <= r: # 必须是 <=，因为如果是 <，nums: [5], target: 5 的情况就cover不了
			m = (l + r) // 2 # (l + r) // 2 may have the over-flow issue in other languages (Python is fine). l + (r - l) // 2 is perfect in all languages
			if target == nums[m]:
				return m
			elif target > nums[m]:
				l = m + 1
			else:
				r = m - 1
		return -1

# brute force 
#  - time: O(max(piles)*piles)
#  - space: O(1)
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        speed = 1
        while True:
            totalTime = 0
            for pile in piles:
                totalTime += math.ceil(pile / speed)
            
            if totalTime <= h:
                return speed
            speed += 1
        return speed

# binary search 
#  - time: O(log(max(piles))*piles)
#  - space: O(1)
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        res = r

        while l <= r:
            k = (l + r) // 2

            totalTime = 0
            for p in piles:
                totalTime += math.ceil(float(p) / k)
            if totalTime <= h:
                res = k
                r = k - 1
            else:
                l = k + 1
        return res      

class TimeMap:
	def __init__(self):
		self.m = {}  # space: O(1)

	def set(self, key: str, value: str, timestamp: int) -> None:
		if key not in self.m:
			self.m[key] = []
		self.m[key].append([timestamp, value])

	def get(self, key: str, timestamp: int) -> str:
		if key not in self.m:
			return ""

		values = self.m[key]
		res = ""
		# Since "All the timestamps timestamp of set are strictly increasing", the timestamps of self.m[<key>] is increasing.
		# Hence, we could use binary search
		l, r = 0, len(values) - 1
		while l <= r:
			m = (l + r) // 2
			if timestamp == values[m][0]:
				return values[m][1]
			elif timestamp < values[m][0]:
				# the timestamp of the current m position is still > the input values[m][0],
				# and hence cannot consider the m position and have to consider the left part,
				# like get("foo",1), [[10, "test1"], [11, "test2"] ...], we return "", since only consider <=1
				r = m - 1
			else:
				# m position has been considered into res, and continue to search the right part
				l = m + 1
				res = values[m][1]
		return res