[Java/C++/Python] Binary Search with Explanation
Intuition\nBinary search\n\n\n# Explanation\nAssume we want give each child m candies, for each pile of candies[i],\nwe can divide out at most candies[i] / m su
# **Intuition**\nBinary search\n<br>\n\n# **Explanation**\nAssume we want give each child `m` candies, for each pile of `candies[i]`,\nwe can divide out at most `candies[i] / m` sub piles with each pile `m` candies.\n\nWe can sum up all the sub piles we can divide out, then compare with the `k` children.\n\nIf `k > sum`, \nwe don\'t allocate to every child, \nsince the pile of `m` candidies it too big,\nso we assign `right = m - 1`.\n\nIf `k <= sum`, \nwe are able to allocate to every child, \nsince the pile of `m` candidies is small enough\nso we assign `left = m`.\n\nWe repeatly do this until `left == right`, and that\'s the maximum number of candies each child can get.\n<br>\n\n# **Tips**\nTip1.  `left < right` Vs `left <= right`\n\nCheck all my solution, I keep using `left < right`.\nThe easy but important approach: \nfollow and upvote my codes,\ntry to do the same.\nyou\'ll find all binary search is similar,\nnever bother thinking it anymore.\n\nTip2. `mid = (left + right + 1) / 2` Vs `mid = (left + right) / 2`\n\n`mid = (left + right) / 2` to find **first** element valid\n`mid = (left + right + 1) / 2 `to find **last** element valid\n<br>\n\n# **Complexity**\nTime `O(nlog10000000)`\nSpace `O(1)`\n<br>\n\n**Java**\n```java\n    public int maximumCandies(int[] A, long k) {\n        int left = 0, right = 10_000_000;\n        while (left < right) {\n            long sum = 0;\n            int mid = (left + right + 1) / 2;\n            for (int a : A) {\n                sum += a / mid;\n            }\n            if (k > sum)\n                right = mid - 1;\n            else\n                left = mid;\n        }\n        return left;\n    }\n```\n\n**C++**\n```cpp\n    int maximumCandies(vector<int>& A, long long k) {\n        int left = 0, right = 1e7;\n        while (left < right) {\n            long sum = 0, mid = (left + right + 1) / 2;\n            for (int& a : A) {\n                sum += a / mid;\n            }\n            if (k > sum)\n                right = mid - 1;\n            else\n                left = mid;\n        }\n        return left;\n    }\n```\n\n**Python**\n```py\n    def maximumCandies(self, A, k):\n        left, right = 0, sum(A) / k\n        while left < right:\n            mid = (left + right + 1) / 2\n            if k > sum(a / mid for a in A):\n                right = mid - 1\n            else:\n                left = mid\n        return left\n```\n<br>\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']