Python Simplest Binary Search Explanation
I haven\'t seen an easy to understand binary search solution, so here is mine. It took me a while of staring at it to figure this out, so hopefully this is help
I haven\'t seen an easy to understand binary search solution, so here is mine. It took me a while of staring at it to figure this out, so hopefully this is helpful for someone else. For an interview, I think the hashmap solution is more intuitive and easier to implement.\n\nThere are 2 key ideas for this problem:\n1) sample uniformly from the interval `[ 0, n - len(blacklist) )`. This ensures every valid response has the same probability of being drawn.\n2) the index in the sorted blacklist tells you how many elements are skipped before the blacklisted element, so if you add the index to the random draw, you\'ll get the result you want. Imagine doing a linear scan through the sorted blacklist for `draw`, you won\'t stop until `blacklist[i] > draw + i`. This is the same condition you want for your binary search. \n\nAs an example:\n```\nn = 7, blacklist = [2, 3, 5]\nRandomly draw from the interval [0, n - len(blacklist) ) -> [0, 4)\n\nBlacklist:      2, 3,    5\nDraw:     0, 1,       2,    3\nOutput:   0, 1, 2, 3, 4, 5, 6\n\nExample: draw = 2\nBlacklist idx: 0, 1, 2\nBlacklist:     2, 3, 5\nDraw + idx:    2, 3, 4\n```\n\n\nThe cleanest flavour of binary search for this problem is the same as `bisect.bisect_right`.\nExplanation of `bisect.bisect_right`: If you have an array of `arr = [0, 0, 2, 2, 4, 4]` `bisect_right` will return the index `i` that splits this array in two, so that if you did `arr[:i]` and `arr[i:]`, the value you\'re searching for would appear on the left array. Searching for value `2` would return index `4`.  (If the value doesn\'t appear, it splits where that element would insert, for example searching for value `3` would return index `4`). \n\nGeneric Bisect-right binary search: the same as binary-searching for the right most insertion point, but adding 1 to the output.\n```\ndef bisect_right(arr: List[int], target: int) -> int:\n\tl, r = 0, len(arr)-1\n\twhile l <= r:\n\t\tm = (l+r)//2\n\t\tif arr[m] <= target:\n\t\t\tl = m+1\n\t\telse:\n\t\t\tr = m-1\n\treturn r+1\n```\n\n\nHere is the full solution, `O(B logB)` construction and `O(logB)` to pick.\n\n```\nclass Solution:\n    def __init__(self, n: int, blacklist: List[int]):\n        self.blacklist = sorted(blacklist)\n        self.max = n - len(blacklist)\n\n    def pick(self) -> int:\n        v = random.randint(0, self.max-1)\n        l, r = 0, len(self.blacklist) - 1\n        while l <= r:\n            m = (l+r)//2\n            if self.blacklist[m] <= v+m:\n                l = m+1\n            else:\n                r = m-1\n        return v + r + 1\n```\n\nNote that you could also convert `arr[m] <= draw + m`  to `arr[m] - m <= draw` which gives the pre-processed blacklist solution: `blacklist = [b - i for i, b in enumerate(blacklist]`. For this case, the solution is simplified if you are willing to use the builtin `bisect` library:\n\n```\nclass Solution:\n    def __init__(self, n: int, blacklist: List[int]):\n        self.blacklist = [b-i for i, b in enumerate(sorted(blacklist))]\n        self.max = n - len(blacklist)\n\n    def pick(self) -> int:\n        v = random.randint(0, self.max-1)\n\t\treturn v + bisect.bisect_right(self.blacklist, v)\n```\n\nOne caveat is that I don\'t think this will work if there are duplicates in `blacklist`. In that case you\'d want to de-dupe in the constructor with something like: `self.blacklist = sorted(set(blacklist))`.
['Binary Tree', 'Python']