Binary Search Explained
Problem Description\n\nImplement a SnapshotArray that supports the following operations:\n\n1. SnapshotArray(length): Initializes an array-like data structure w
## Problem Description\n\nImplement a SnapshotArray that supports the following operations:\n\n1. `SnapshotArray(length)`: Initializes an array-like data structure with the given length. Initially, each element equals 0.\n2. `set(index, val)`: Sets the element at the given index to be equal to `val`.\n3. `snap()`: Takes a snapshot of the array and returns the `snap_id`: the total number of times `snap()` has been called minus 1.\n4. `get(index, snap_id)`: Returns the value at the given index, at the time the snapshot with the given `snap_id` was taken.\n\n## Approach Explanation\n\n- **SnapshotArray Overview**:\n  - Use an array of lists (`arr`) to maintain the history of each element\'s value changes.\n  - Each element in `arr` corresponds to an index in the array and contains a list of `[value, snap_id]` pairs representing the value at that index and the snap_id when it was set.\n  - Maintain a `snaps` counter to keep track of the number of snapshots taken.\n  \n- **set(index, val) Operation**:\n  - Append the `[val, snaps]` pair to the list at the specified index in `arr` to record the new value set at that index.\n\n- **snap() Operation**:\n  - Increment the `snaps` counter and return the current `snaps - 1` as the `snap_id`.\n\n- **get(index, snap_id) Operation**:\n  - Retrieve the list of values recorded at the specified index.\n  - Perform a binary search within the list to find the most recent value at or before the given `snap_id`.\n  - Return the corresponding value from the list.\n\n- **Complexity Analysis**:\n  - `SnapshotArray(length)`: O(length) time complexity for initialization.\n  - `set(index, val)`: O(1) average time complexity to append a value to the list.\n  - `snap()`: O(1) time complexity to increment the `snaps` counter.\n  - `get(index, snap_id)`: O(log k) time complexity for binary search, where `k` is the number of snapshots recorded for the index.\n\n```python\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.snaps = 0\n        self.arr = [] \n        for i in range(length):\n            self.arr.append([])\n\n    def set(self, index: int, val: int) -> None:\n        self.arr[index].append([val, self.snaps]) \n\n    def snap(self) -> int:\n        self.snaps += 1\n        return self.snaps - 1\n\n    def get(self, index: int, snap_id: int) -> int:\n        values = self.arr[index]\n        res = 0\n        start, end = 0, len(values) - 1\n        while start <= end:\n            mid = (start + end) >> 1\n            if values[mid][1] <= snap_id:\n                res = values[mid][0]\n                start = mid + 1\n            else:\n                end = mid - 1\n        return res\n```\n> #### ***If You Found it helpful, please upvote it. Thanks***\n![Image](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)\n\n
['Array', 'Binary Search', 'Design', 'Python3']