C++ | Binary Search
IntuitionMy Current intuition was to use recursive function where we have two choices:
Rob the current house (but then we must skip the next house).
Skip the cu
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
My Current intuition was to use recursive function where we have two choices:

1. Rob the current house (but then we must skip the next house).
2. Skip the current house and move forward.

And then turn this function to DP where we need an additional condition—ensuring that we rob at least k houses. The dynamic programming solution involves a state dp[houseIndex][numberOfHousesRobbed]. Since we iterate over n houses and track up to k robbed houses, the problem becomes more complex, and solving it with dynamic programming takes O(n⋅k) time.
# Approach
<!-- Describe your approach to solving the problem. -->
Never ever I would've thought this could be solved using Binary Search so I tried reading the editorial, some solutions and then some youtube videos where I found that Problems that require minimizing the maximum or maximizing the minimum often suggest a binary search approach. Instead of searching through indices or subsets directly, we can binary search on the capability

So using the binary search template we Binary search the minimum capability of the robber to steal at least k houses. Given 1 <= nums[i] <= 1e9, we can initial the binary search range as left = 1 and right = 1e9. We can also set left = min(nums) and right = max(nums).

Assume the capability is mid, we iterate the houses A, and greedily take the houses as many as possible, if mid > nums[i] and we didn't take nums[i-1].

Then we check if we have take k houses,If take >= k,we have big enough capability,right = mid.If take < k,we don't have big enough capability,left = mid + 1. Finally we return the binary search result.

# Complexity
- Time complexity: O(nlogm), where m is the range of nums[i]
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
# Code
```cpp []
class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int left = 1;
        int right = 1e9;
        int n = nums.size();
        while(left < right){
            int mid = (left + right) / 2;
            int take = 0;
            for(int i = 0; i < n; i++){
                if(nums[i] <= mid){
                    take += 1;
                    i++;
                }
            }
            if(take >= k){
                right = mid;
            } else{
                left = mid + 1;
            }
        }
        return left;
    }
};
```
['C++']