# solution 1 - burte force
# time: O(n)

# solution 2 - 写法1 time: O(logn)
	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
  
# solution 2 - 写法2  
	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

# 写法 1
	# time: O(logn)
	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
  
# 写法2 - more elegent
	# time: O(logn)
	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]

	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

# solution 1 - more elegent
	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

	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
			if target == nums[m]:
				return m
			elif target > nums[m]:
				l = m + 1
			else:
				r = m - 1
		return -1

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