Math proof of the Binary search on the answer approach
ApproachBinary search on the answerproofsExampleCodeComplexity

Time complexity:
O(n log hi)


Space complexity:
O(1)

# Approach
Binary search on the answer

# proofs
![image.png](https://assets.leetcode.com/users/images/4f814cd9-f1d7-4e4b-a000-3714a3b36735_1742075814.7710013.png)

![image.png](https://assets.leetcode.com/users/images/4563e0a9-416a-49ea-ab0a-bd537f224582_1742075832.947159.png)

![image.png](https://assets.leetcode.com/users/images/fe992d79-7767-4a6b-8cf5-8028efdc38f9_1742075913.8819184.png)

![image.png](https://assets.leetcode.com/users/images/203fe2b7-1676-4266-9d1f-4eb5dbcc9a4b_1742075940.318759.png)

![image.png](https://assets.leetcode.com/users/images/8ad31654-8d8f-4f64-bc93-b98c995f15ac_1742075953.5684204.png)

# Example
![image.png](https://assets.leetcode.com/users/images/0c2478c4-1185-43d2-924c-1499b81e7042_1742082391.5753894.png)


# Code
```cpp []
class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int n=nums.size();
        int hi=*std::max_element(nums.begin(),nums.end());

        auto is_possible=[&](int capability)->bool{
            int robbed_houses=0;
            int i=0;
            while(i<n){
                if(nums[i]<=capability){
                    robbed_houses++;
                    i+=2;
                }
                else i++;
                if(robbed_houses>=k) return true;
            }
            return false;
        };

        int lo=1;
        while(lo<hi){
            int capability=(lo+hi)>>1;
            if(is_possible(capability)) hi=capability;
            else lo=capability+1;
        }
        return lo;    
    }
};
```

# Complexity
- Time complexity:
O(n log hi)

- Space complexity:
O(1)
['C++']