[Java/C++/Python] Binary Search O(1) Space
Intuition\nHey Robber series,\nold school DP problem,\nI practiced thousands of times.\n\nWait, in classical Robber problem,\nwe usually want to maximize the va
# **Intuition**\nHey Robber series,\nold school DP problem,\nI practiced thousands of times.\n\nWait, in classical Robber problem,\nwe usually want to maximize the value to steal.\n\nHere we want to minimize the maximum house we steal.\nSo it\'s not a robber-like problem,\nit\'s actually a mini-max problem.\n\nWhen we mini-max one capacity to do something,\n(here is robber `k` houses)\nwe can use bianry search.\n\nWhen use binary search,\nI suggest you using my template\n```\nwhile (left < right) {\n    int mid = (left + right) / 2;\n    if (condition)\n        right = mid;\n    else\n        left = mid + 1;\n}\nreturn left;\n```\n\n<br>\n\n# **Explanation**\nBinary search the minimum capability of the robber\nto steal at least `k` houses.\n\nGiven `1 <= A[i] <= 1e9`,\nwe can initial the binary search range as\n`left = 1` and `right = 1e9`.\nwe can also set `left = min(A)` and `right = max(A)`.\n\nAssume the capability is `mid`,\nwe iterate the houses `A`,\nand greedily take the houses as many as possible,\nif `mid > A[i]` and we didn\'t take `A[i-1]`.\n\nThen we check if we have take `k` houses,\nIf `take >= k`,\nwe have big enough capability,\n`right = mid`.\nIf `take < k`,\nwe don\'t have big enough capability,\n`left = mid + 1`.\n\nFinally we return the binary search result.\n<br>\n\n# **Complexity**\nTime `O(nlogm)`,\nwhere `m` is the range of A[i]\nSpace `O(1)`\n\nWe can also binary search the value in `sorted(set(A))`,\nTime `O(nlogn)`,\nSpace `O(n)`.\n<br>\n\n**Java**\n```java\n    public int minCapability(int[] A, int k) {\n        int left = 1, right = (int)1e9, n = A.length;\n        while (left < right) {\n            int mid = (left + right) / 2, take = 0;\n            for (int i = 0; i < n; ++i)\n                if (A[i] <= mid) {\n                    take += 1;\n                    i++;\n                }\n            if (take >= k)\n                right = mid;\n            else\n                left = mid + 1;\n        }\n        return left; //left == right\n    }\n```\n\n**C++**\n```cpp\n    int minCapability(vector<int>& A, int k) {\n        int left = 1, right = 1e9, n = A.size();\n        while (left < right) {\n            int mid = (left + right) / 2, take = 0;\n            for (int i = 0; i < n; ++i)\n                if (A[i] <= mid) {\n                    take += 1;\n                    i++;\n                }\n            if (take >= k)\n                right = mid;\n            else\n                left = mid + 1;\n        }\n        return left; //left == right\n    }\n```\n\n**Python**\n```py\n    def minCapability(self, A: List[int], k: int) -> int:\n        l, r = min(A), max(A)\n        while l < r:\n            m = (l + r) // 2\n            last = take = 0\n            for a in A:\n                if last:\n                    last = 0\n                    continue\n                if a <= m:\n                    take += 1\n                    last = 1\n            if take >= k:\n                r = m\n            else:\n                l = m + 1\n        return l\n```\n\n# More Good Binary Search Problems\nHere are some similar binary search problems.\nAlso find more explanations.\nGood luck and have fun.\n\n- 2226. [Maximum Candies Allocated to K Children](https://leetcode.com/problems/maximum-candies-allocated-to-k-children/discuss/1908888/JavaC%2B%2BPython-Binary-Search-with-Explanation)\n- 1802. [Maximum Value at a Given Index in a Bounded Array](https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/discuss/1119801/Python-Binary-Search)\n- 1539. [Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/discuss/779999/JavaC++Python-O(logN))\n- 1482. [Minimum Number of Days to Make m Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/discuss/686316/javacpython-binary-search)\n- 1283. [Find the Smallest Divisor Given a Threshold](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/discuss/446376/javacpython-bianry-search)\n- 1231. [Divide Chocolate](https://leetcode.com/problems/divide-chocolate/discuss/408503/Python-Binary-Search)\n- 1011. [Capacity To Ship Packages In N Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/discuss/256729/javacpython-binary-search/)\n- 875. [Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/discuss/152324/C++JavaPython-Binary-Search)\n- 774. [Minimize Max Distance to Gas Station](https://leetcode.com/problems/minimize-max-distance-to-gas-station/discuss/113633/Easy-and-Concise-Solution-using-Binary-Search-C++JavaPython)\n- 410. [Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/)\n<br>\n
['C', 'Python', 'Java']