🔥Binary Search✅| Beginner Friendly | Java | C++
Intuition
The problem requires selecting non-adjacent houses such that the minimum among the chosen houses values is maximized while ensuring at least k houses
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- The problem requires selecting non-adjacent houses such that the minimum among the chosen houses values is maximized while ensuring at least k houses are selected. The goal is to find the smallest possible value (minCapability) such that we can still rob at least k houses.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Binary Search on the Minimum Capability

- First, create a sorted copy of the original array (b[]) to determine the possible range of the minimum capability: l = min(a), r = max(a).
- Perform a binary search on this range.
- For each middle value (mid), check if it is possible to rob at least k houses using this as the maximum allowed house value.

2. Greedy Checking (robbinghouses function)

- Iterate through the array and greedily select houses with values ≤ mid, ensuring non-adjacent selection.
- If at least k houses can be robbed, update the answer and search for a smaller mid.
- Otherwise, search for a larger mid.
3. Binary Search Adjustment

- If we can rob k houses with mid, search in the left half (r = mid - 1) to minimize the capability.
- Otherwise, search in the right half (l = mid + 1).
- The final answer is stored in ans.

# Complexity
Time complexity:
=
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Sorting takes O(n log n).
- Binary search operates in O(log max(a)).
- Each check (robbinghouses function) runs in O(n).
- Total complexity: O(n log n) + O(n log max(a)) ≈ O(n log n).

Space complexity:
=
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
- O(n) for storing the sorted copy of the array.
- O(1) extra space apart from input storage.

# Code in C++
```C++ []
class Solution {
public:
    int minCapability(vector<int>& a, int k) {
        vector<int> b = a;
        sort(b.begin(), b.end());
        int l = b[0], r = b.back(), mid, ans = r;

        while (l <= r) {
            mid = l + (r - l) / 2;
            int x = robbingHouses(a, mid, k);
            if (x >= k) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

public:
    int robbingHouses(vector<int>& a, int val, int k) {
        int count = 0;
        for (int i = 0; i < a.size();) {
            if (a[i] <= val) {
                count++;
                i += 2;
            } else {
                i++;
            }
        }
        return count;
    }
};

```
# Code in Java
```java []
class Solution {
    public int minCapability(int[] a, int k) {
        int b[]=Arrays.copyOf(a,a.length);
        Arrays.sort(b);
        int l=b[0],r=b[a.length-1],mid,ans=r;

        while(l<=r)
        {
            mid=l+(r-l)/2;
            int x=robbinghouses(a,mid,k);
            if(x>=k)
            {
                ans=mid;
                r=mid-1;
            }
            else
            l=mid+1;
        }
        return ans;
    }
    public int robbinghouses(int[] a,int val,int k)
    {
        int i,count=0;
        for(i=0;i<a.length;)
        {
            if(a[i]<=val)
            {
            count++;
            i+=2;
            }
            else
            i++;
        }
        return count;
    }
}
```
['Array', 'Binary Search', 'C++', 'Java']