Aller au contenu principal

Binary Search

n is the number of elements in nums list.

Time Complexity: O(logn), because we split the nums list half each time, we can split at most log2(n) times.

Space Complexity:

def search(nums: List[int], target: int) -> int:
  l, r = 0, len(nums) - 1
  mid = (l + r) // 2

  while l <= r:
    mid = (l + r) // 2
    if nums[mid] < target:
      l = mid + 1
    elif nums[mid] > target:
      r = mid - 1
    else:
      break
  return mid if nums[mid] == target else -1

74 Search a 2D Matrix​

875 Koko Eating Bananas​

def minEatingSpeed(piles: List[int], h: int) -> int:
  l, r = 1, max(piles)
  res = r

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

    for pile in piles:
      total_time += - ( - pile // k)
    
    if total_time <= h:
      res = k
      r = k - 1
    else:
      l = k + 1
  return res

153 Find Minimum in Rotated Sorted Array​

class Solution:
  def findMin(self, nums: List[int]) -> int:
    l, r = 0, len(nums) - 1

    while l < r:
      mid = (l + r) // 2
      if nums[mid] > nums[r]:
        l = mid + 1
      else:
        r = mid
    return nums[l]

981 Time based Key Value Store​

class TimeMap:
  def __init__(self):
     self.table = {}  # {key: [timestamp, value]
    
  def set(self, key:str, value: str, timestamp: str) -> None:
    if key in self.table:
      self.table[key].append([timestamp, value])
    else:
      self.table[key] = [[timestamp, value]]
      
  def get(self, key:str, timestamp: str) -> str:
    if key in self.table:
      l, r = 0, len(self.table[key]) - 1

      while l <= r:
        mid = (l + r) // 2
        if self.table[key][mid][0] <= timestamp:
          l = mid + 1
        else:
          r = mid - 1
      
      return self.table[key][mid][1] 
    else:
      return ""