[JavaScript] Binary Search
For set: To save space, we store a new version of data only when the current version is higher than the oldest version present in an index\'s history. If the la
For `set`: To save space, we store a new version of data only when the current version is higher than the oldest version present in an index\'s history. If the latest version in an index\'s history matches our current version, then we simply update what\'s in our history in-place.\n\nFor `get`: Now that we are storing historical values and their version numbers in each index-specific array, the problem can be reworded as, "given a target number and a sorted array, return the floor value, i.e., the largest number that is either the same or smaller than the target." For example, imagine that we were given an array of version numbers, like this: `[0,3,4,5]` . If the target were `3`, we\'d just return `3`. But if the target were `2`, then we need to return `0`, because that\'s the latest version up until `3`.  \n\nAs an exercise, I recommend you to try to implement the above task using binary search. You\'ll notice that it\'s not possible (or at least really hard) to find the floor value directly by binary search. You should instead find the ceiling value, i.e., the smallest number that is either the same or larger than the target, and then try to find the floor value (which is either the same as the ceiling value -- if the target is present in the array -- or is located directly on the left of the ceiling val).\n\nOne edge case is if the array were  `[0,3,4,5]`, and the version we\'re looking for is `7`. In this case, the array does not contain the ceiling value. So before doing binary search, we should check that the target version isn\'t greater than the latest version in history.\n\n```js\nvar SnapshotArray = function(length) {\n    this.snapId = 0\n    this.arr = new Array(length)\n    for (let i = 0; i < this.arr.length; i++) {\n        this.arr[i] = [[0,0]] // add snapId, val\n    }\n};\n\nSnapshotArray.prototype.set = function(index, val) {\n    const arrAtIdx = this.arr[index]\n    const lastIdx = arrAtIdx.length - 1\n    const lastSnapId = arrAtIdx[lastIdx][0]\n    if (lastSnapId === this.snapId) {\n        // update\n        arrAtIdx[lastIdx][1] = val\n    } else {\n        // push new\n        arrAtIdx.push([this.snapId, val])\n    }\n};\n\nSnapshotArray.prototype.snap = function() {\n    this.snapId++\n    \n    return this.snapId - 1\n};\n\nSnapshotArray.prototype.get = function(index, snap_id) {\n    // find floor val (aka the largest snap_id in history that is smaller or equal to the target snap_id)\n    // in order to find floor val, we need to first find ceiling val (aka the smallest snap_id in history that is larger or equal to the target snap_id)\n    const arrAtIdx = this.arr[index]\n    \n    // edge case:\n    // this means everything in the arrAtIdx has lower snap_id than the target snap_id,\n    // so just return the latest version\n    if (arrAtIdx[arrAtIdx.length - 1][0] < snap_id) {\n        return arrAtIdx[arrAtIdx.length - 1][1]\n    }\n    \n    let lo = 0\n    let hi = arrAtIdx.length - 1\n    while (lo < hi) {\n        const mid = lo + Math.floor((hi - lo) /2)\n        if (arrAtIdx[mid][0] >= snap_id) {\n            hi = mid\n        } else {\n            lo = mid + 1\n        }\n    }\n\n    // hi is at ceiling\n    if (arrAtIdx[hi][0] === snap_id || hi === 0) {\n        return arrAtIdx[hi][1]   \n    }\n    \n    // hi - 1 must be the floor\n    return arrAtIdx[hi - 1][1]\n};\n```
['JavaScript']