[Java] Binary Search WITHOUT TreeMap
Use a List[] data structure to save [snap_id, val] pair. Each time when the set(int index, int val) method is called, adding the new [snap_id, val] pair into co
Use a **List<int[]>[]** data structure to save [**snap_id**, **val**] pair. Each time when the **set**(int index, int val) method is called, adding the new [snap_id, val] pair into corresponding list.\n```\nclass SnapshotArray {\n    public List<int[]>[] h;\n    public int snap = 0;\n    public SnapshotArray(int length) {\n        h = new List[length];\n        for (int i = 0; i < length; i++) {\n            h[i] = new ArrayList<>();\n            // add an initial [snap_id, val] pair, very important\n            h[i].add(new int[]{-1, 0});\n        }\n    }\n    \n    public void set(int index, int val) {\n        h[index].add(new int[]{snap, val});\n    }\n    \n    public int snap() {\n        return snap++;\n    }\n    \n    public int get(int index, int snap_id) {\n        List<int[]> temp = h[index];\n        int l = 0, r = temp.size() - 1;\n        // binary search rightmost\n        while (l < r) {\n            int m = r - (r - l) / 2;\n            if (temp.get(m)[0] <= snap_id) l = m;\n            else r = m - 1;\n        }\n        return temp.get(l)[1];\n    }\n}\n\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```
['Binary Tree', 'Java']