Python binary search O(lgn) and linear search O(n)
If we don\'t take initialization into account, the time complexity of the binary search would be O(lgn)\n\nLinear seach O(n)\n\nclass RLEIterator:\n\n    def __
If we don\'t take initialization into account, the time complexity of the binary search would be O(lgn)\n\nLinear seach O(n)\n```\nclass RLEIterator:\n\n    def __init__(self, encoding: List[int]):\n        self.a = encoding\n        self.idx = 0\n            \n\n    def next(self, n: int) -> int:\n        while self.idx + 1 < len(self.a):\n            f, num = self.a[self.idx], self.a[self.idx + 1]\n            if n > f:\n                n -= f\n                self.idx += 2\n            elif n == f:\n                self.idx += 2\n                return num\n            else:\n                self.a[self.idx] -= n\n                return num\n        return -1\n```\nBineary search O(lgn)\n```\nclass RLEIterator:\n\n    def __init__(self, encoding: List[int]):\n        self.idx = i = 0\n        self.arr = [] # accumulative sum of the number of elements\n        self.num = []\n        count = 0\n        while i < len(encoding):\n            f, num = encoding[i], encoding[i + 1]\n            i += 2\n            if f == 0: # skip 0\n                continue\n            count += f\n            self.arr.append(count)\n            self.num.append(num)\n            \n\n    def next(self, n: int) -> int:\n        self.idx += n\n        i = bisect.bisect_left(self.arr, self.idx)\n        return self.num[i] if i < len(self.arr) else -1\n        \n```
['Binary Tree', 'Python']