C++ || Easy || Binary Search
Intuition\n Describe your first thoughts on how to solve this problem. \nTo store the array elements in the least possible space, a list of lists is the ideal a
## Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo store the array elements in the least possible space, a list of lists is the ideal approach. To increase the efficiency of the searching algorithm (particularly the ```get()``` function), use binary search.\nThis approach uses a map to increase the efficiency of the searching (indexing) process. You can use a ```vector<vector<pair<int,int>>>``` as well for the same purpose.\n\n## Approach\n<!-- Describe your approach to solving the problem. -->\n1. Create a list of lists of pairs of integers (done here using ```map<int,vector<pair<int,int>>>```) to store the elements and the corresponding snap_id for each change introduced to the elements.\n2. Initialise a variable, ```sn```, to store the latest snap_id.\n3. For the constructor, push a new pair ```{0,0}``` to each list in the parent list.\n4. For the ```set()``` function, corresponding to the given index, check if the last entry corresponds to the current snap:\n    - If yes, the value previously stored (i.e. the last element of ```m[index]```) is not important and can be erased. So overwrite the element entry to store the new value.\n    - Else, push a new value, ```{value,sn}``` to the list corresponding to index (i.e. ```m[index]```).\n5. For the ```snap()``` function, return ```sn``` and increment it by 1.\n6. For the ```get()``` function:\n    - If the first element ```m[index]``` corresponds to the required ```snap_id``` then return ```m[index][0].first```\n    - Else, perform a binary search on the list ```m[index]``` and find the element corresponding to the required ```snap_id``` as either ```m[index][i].second==snap_id```, or ```m[index][i].second<snap_id && m[index][i+1].second>snap_id```.\n    - If the binary search terminates without finding the required element, return ```m[index][m.size()-1].first``` i.e. the last element of the list corresponding to ```index``` (since this means that the element has not been updated between the last snap and this snap).\n\n## Complexity\n- Time complexity: *O(log(length))*\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: *O(length.sn)*\n*(Here sn represents the highest snap_id)*\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n## Code\n```cpp []\n/*\n * Your SnapshotArray object will be instantiated and called as such:\n * SnapshotArray* obj = new SnapshotArray(length);\n * obj->set(index,val);\n * int param_2 = obj->snap();\n * int param_3 = obj->get(index,snap_id);\n*/\n\nclass SnapshotArray {\n    map<int,vector<pair<int,int>>> m;\n    int sn = 0;\npublic:\n    SnapshotArray(int length) {\n        for(int i=0; i<length; i++) m[i].push_back({0,sn});\n    }\n    \n    void set(int index, int val) {\n        if(m[index][m[index].size()-1].second==sn)\n            m[index][m[index].size()-1].first = val;\n        else\n            m[index].push_back({val,sn});\n    }\n    \n    int snap() {\n        return sn++;\n    }\n    \n    int get(int index, int snap_id) {\n        if(m[index].size()==1 || m[index][0].second==snap_id)\n            return m[index][0].first;\n        \n        int l = 0, r = m[index].size()-1;\n        while(l<=r){\n            int mid = (l+r)/2;\n            if(mid==m[index].size()-1)\n                return m[index][m[index].size()-1].first;\n            if(m[index][mid].second<=snap_id && m[index][mid+1].second>snap_id)\n                return m[index][mid].first;\n            else if(m[index][mid].second>snap_id)\n                r = mid-1;\n            else\n                l = mid+1;\n        }\n\n        return m[index][m[index].size()-1].first;\n    }\n};\n```
['Array', 'Hash Table', 'Binary Search', 'Design', 'C++']