[Python] Binary Search + Find the Majority Element
Basic Idea\nFor each a in A, save its index of occurrence to list a2i[a].\nWhen we want to get the exact occurrence of a in a range,\nwe can use binary search i
## Basic Idea\nFor each `a` in `A`, save its index of occurrence to list `a2i[a]`.\nWhen we want to get the exact occurrence of `a` in a range,\nwe can use binary search in `a2i[a]`.\n\nIn the general good cases,\nthe numbers in `A` should be various,\neach number should appear 1 time in average,\nmaking the time complexity only `O(1)`.\n\nIn the specific worst cases to this binary search solution,\nthe cases will be something like `[1,2,1,2,1,2,1,2....]`,\nmaking the binary search `O(logN)`, (search in a list of length `N / 2`).\n\nNow the only problem we need to solve,\nis that how to find the majority element if it exists.\n<br>\n\n## Solution 1: Random Pick\n\nRandom Pick number `a` from the range of query.\nIf there is a majority element,\nwe have >50% chance to get it for each pick.\n\nHere I random pick 20 times,\nbecause there are at most 10000 queries and 2^20 = 1048576 is much bigger than 10000.\n\nIf there is a majority element,\nI only have `1/(2^20)` possibility to miss it.\nAnd we\'ll query at most 10000 times,\nthe expectation of fail times is about 0.01 time,\nwhich sounds good.\n\nI have used the same idea in [961. N-Repeated Element in Size 2N Array](https://leetcode.com/problems/n-repeated-element-in-size-2n-array/discuss/208563/JavaC%2B%2BPython-O(1)-Solution)\nThe funny thing that, I was criticized this idea is misleading earlier this week.\nWell thanks this guy and I recalled this idea immediately.\n\nComplexity of function `query`:\nTime `O(20logN)` for binary searching (or `O(logNlogN)`)\nSpace `O(1)`\n\nActually `O(20lgn)` is the same as `O(logNlogN)`.\nWe just need to pick `k` times and then let `2^k >> n`.\n<br>\n\n**Python:**\n```python\nclass MajorityChecker(object):\n\n    def __init__(self, A):\n        a2i = collections.defaultdict(list)\n        for i, x in enumerate(A):\n            a2i[x].append(i)\n        self.A, self.a2i = A, a2i\n\n    def query(self, left, right, threshold):\n        for _ in xrange(20):\n            a = self.A[random.randint(left, right)]\n            l = bisect.bisect_left(self.a2i[a], left)\n            r = bisect.bisect_right(self.a2i[a], right)\n            if r - l >= threshold:\n                return a\n        return -1\n```\n<br>\n\n## Solution 2: Bucket\nFor each bucket of size `sqrt(N)`,\nfind the majority candidate using [Boyer\u2013Moore majority vote algorithm](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm).\n\nThe idea is that, the element that has over half occurrence,\nmust be the majority element in at least one bucket.\n\nNow for any range of `query`,\nthere are at most `sqrt(N)` bucket involved,\n(For the elements not in the bucket, we vote for one candidate.)\nSo we have at most `sqrt(N)` candidates.\n\nWe check the occurrence for each candidate using the basic idea above.\n\nComplexity of initialization:\nTime `O(N)`\nSpace `O(N)`\n\nComplexity of function `query`:\nTime `O(sqrtN * logN)`\nSpace `O(1)`\n<br>\n\n## Solution 3: Segment Tree\nFor any range,\nfind the majority candidate of sub range,\nthen merge the two majority candidates.\nusing the idea of [Boyer\u2013Moore majority vote algorithm](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm).\n\nComplexity of initialization:\nTime `O(N)`\nSpace `O(N)`\n\nComplexity of function `query`:\nTime `O(logN)`\nSpace `O(1)`\n<br>
[]