Binary Search (C++) with Similar Problems
Intuition\n Describe your first thoughts on how to solve this problem. \nThese question screams Binary Search\n\nThis problem asks for maximum-minimum problem (
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**These question screams Binary Search**\n\nThis problem asks for **maximum-minimum** problem (thief has capability **maximum** of all houses robbed and we want to identify that way to make it as **minimum** as possible)\n\n# Reason:\n1) We want to find the minimum possible value and capability should be maximum of all selected.\n2) if we try to think greedy way then we are done unless we define a limit **Mid** such that no element choosen be greater than Limit. (**Binary Search**)\n3) In general when you will go through the list of bindary search questions, you will observe that questions in which minima-maxima or maxima-minima is asked they are solved by Binary search problems.\n    \n# Approach\n\n* **Mid** will define the limit, our element should be smaller than this limit.\n\n* Iterate over the array and pic any k non-adjacent elements that are smaller than our limit( **Mid** in our case).\n   \n* Some of you might be thinking that me wondering why here i have used one loop only well lets observe:\n\n* If I have **$$nums[i]<=limit$$** and $$nums[i+1]<=limit$$, if I choose ith element I will have $$n-i-1$$ more choices from $$i+2<=x<n$$. Here, x represents the candidates i can choose. If I choose $$i+1 th$$ element I will have $$n-i-2$$ element to choose from $$i+3<=x<n$$ so first one is better which boils down to choosing the first element every time i get an element within allowable limit.\n**(Hence there is a greedy way of selecting houses)**\n# Complexity\n- Time complexity:**O(nlogn)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:**O(1)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    bool calc(vector<int>& nums, int k,int mid)\n    {\n        int i=0,n=nums.size();\n        while(i<n)\n        {\n            if(nums[i]<=mid)k--, i+=2;\n            \n            else i++;\n            \n            if(k == 0) return true;\n        }\n        return k == 0;\n    }\n    int minCapability(vector<int>& nums, int k) \n    {\n        int n = nums.size();\n        int lo = 0,hi = 1e9+1;\n        while(lo<hi)\n        {\n            int mid = (lo+hi)/2;\n            if(calc(nums, k, mid)) hi=mid;\n            else lo=mid+1;\n        }\n        return lo;\n    }\n};\n```\n# Similar Problems:\n1) [1760. Minimum Limit of Balls in a Bag](https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/)\n2) [875. Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/).\n3) [1954. Minimum Garden Perimeter to Collect Enough Apples](https://leetcode.com/problems/minimum-garden-perimeter-to-collect-enough-apples/).\n4) [2226. Maximum Candies Allocated to K Children](https://leetcode.com/problems/maximum-candies-allocated-to-k-children/).\n5) [1283. Find the Smallest Divisor Given a Threshold](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/).\n6) [1482. Minimum Number of Days to Make m Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)\n7) [2009. Minimum Number of Operations to Make Array Continuous](https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/)\n8) [2528. Maximize the Minimum Powered City](https://leetcode.com/problems/maximize-the-minimum-powered-city/description/) suggested by @20ryanc\n9) [1552. Magnetic Force Between Two Balls](https://leetcode.com/problems/magnetic-force-between-two-balls/)suggested by @hereToRock
['Binary Search', 'C++']