Python Binary Search
The correct solution to this is using binary search. Please ignore all the people using .copy(). If you do that in an interview, you will definitely fail.\n\n# 
The correct solution to this is using binary search. Please ignore all the people using `.copy()`. If you do that in an interview, you will definitely fail.\n```\n# nums = {}\n# nums[index] = []\n# nums[index][i] = (snap_id, val)\n# set replaces current val if snap_id == nums[index][-1][0]\n# else set appends current val and snap_id\n# snap just increments snap_id and returns old snap_id\n# get does a binary search on nums[index] for the target snap_id and returns the associated value\n\n# nums[5] = [(15, 4)]\n# get(5, 13) => 0\n# get(5, 16) => 4\n\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.snap_id = 0\n        self.nums = defaultdict(list)\n\n    def set(self, index: int, val: int) -> None:\n        if not self.nums[index] or self.nums[index][-1][0] < self.snap_id:\n            self.nums[index].append((self.snap_id, val))\n        else:\n            self.nums[index][-1] = (self.snap_id, val)\n\n    def snap(self) -> int:\n        self.snap_id += 1\n        return self.snap_id - 1\n\n    def get(self, index: int, snap_id: int) -> int:\n        l, r = 0, len(self.nums[index])\n        while l < r:\n            m = (l + r) // 2\n            if self.nums[index][m][0] == snap_id:\n                return self.nums[index][m][1]\n            elif self.nums[index][m][0] < snap_id:\n                l = m + 1\n            else:\n                r = m\n        if l == 0:\n            return 0\n        return self.nums[index][l-1][1]\n```
['Binary Search', 'Python', 'Python3']