Python3 binary search
We simply add [snap_id, val] to each the list at each index. When we retrive the value at snap_id, we use binary search to find the value.\nNotice that we are t
We simply add [snap_id, val] to each the list at each index. When we retrive the value at snap_id, we use binary search to find the value.\nNotice that we are trying to locat the right most value for each snap_id. e.g. [1, 4], [1, 3], [1, 6], we want to get 6 because it is the latest at the snap_id = 1.\n```\nclass SnapshotArray(object):\n\n    def __init__(self, length):\n        """\n        :type length: int\n        """\n        self.snap_id = 0\n        self.list = [[[-1, 0]] for _ in range(length)]\n\n    def set(self, index, val):\n        """\n        :type index: int\n        :type val: int\n        :rtype: None\n        """\n        \n        self.list[index].append([self.snap_id, val])\n        \n    def snap(self):\n        """\n        :rtype: int\n        """\n        ans = self.snap_id\n        self.snap_id += 1\n        return ans\n    \n    def get(self, index, snap_id):\n        """\n        :type index: int\n        :type snap_id: int\n        :rtype: int\n        """\n        #print(self.list)\n        li = self.list[index]\n        left, right = 0, len(li) - 1\n        while left + 1 < right:\n            mid = (left + right) // 2\n            if li[mid][0] <= snap_id:\n                left = mid\n            else:\n                right = mid\n        if li[right][0] <= snap_id:\n            return li[right][1]\n        return li[left][1]\n```\n\nPlease upvote if you find it helpful. Thanks!
['Binary Search', 'Binary Tree', 'Python', 'Python3']