✅🔥WHY Binary Search? (WHY NOT DP?)🔥| Visualization ✨| Math | C++
The goal is to choose exactly k non-adjacent numbers from the array such that the maximum among them (the "capability") is minimized.Intuition & Approach (DP)Id
The goal is to choose exactly k non-adjacent numbers from the array such that the maximum among them (the "capability") is minimized.

---


# Intuition & Approach (DP)
<!-- Describe your first thoughts on how to solve this problem. -->
**Idea:**
We try every possibility using recursion by deciding at each index whether to take the current number (which forces us to skip the next number) or to skip it.
For every decision, we keep track of how many numbers we still need to pick.

**Recurrence:**
Let dp(ind, k) be the minimum achievable "capability" (i.e. the maximum selected value) when starting from index ind with k picks remaining.
There are two choices:

- Take the current element:
If we take nums[ind], then the capability for that path becomes
max(nums[ind], dp(ind + 2, k - 1))
- Skip the current element:
Simply try dp(ind + 1, k).
We return the minimum of these two choices.

**Base Cases:**

- If k == 0, we have successfully chosen exactly k elements and return 0 (no further cost).
- If there aren’t enough remaining elements to select k numbers (i.e. nums.size() - ind < k), return INT_MAX to mark that path as invalid.



---


# Complexity
**Time complexity: O(n*k)**
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
The number of states is roughly O(n * k). However, each state branches into up to 2 recursive calls. Even with memoization, if n and k are large, the constant factors and recursion overhead can be significant.
- Why it may TLE:
In worst-case scenarios with large input sizes, the DP approach (even with memoization) could exceed the time limits due to the depth of recursion and the overlapping subproblems that have to be recomputed or stored.

---

# Code (DP)
```cpp []
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
    int rec(vector<int>& nums, int ind, int k, vector<vector<int>>& dp) {
        if (k == 0) return 0;
        if (ind >= nums.size() || (nums.size() - ind) < k) return INT_MAX;
        if (dp[ind][k] != -1) return dp[ind][k];
        
        // Option 1: Take the current element.
        int take = rec(nums, ind + 2, k - 1, dp);
        if (take != INT_MAX)
            take = max(nums[ind], take);
        else
            take = INT_MAX;
        
        // Option 2: Skip the current element.
        int skip = rec(nums, ind + 1, k, dp);
        
        return dp[ind][k] = min(take, skip);
    }
public:
    int minCapability(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(k + 1, -1));
        return rec(nums, 0, k, dp);
    }
};

```

---
# Intuition: (Binary Search)
- Problem Nature:
You are given an array of numbers and need to select k non-adjacent numbers such that the maximum value among the selected numbers (the “capability”) is minimized.

- Binary Search on Answer:
Instead of directly trying every possible combination (which can be very slow), we can "guess" a candidate capability value and then check if it's possible to pick k numbers that do not exceed this candidate.
This is a typical "minimize the maximum" problem where binary search on the answer works well.

- Feasibility Check (Greedy):
The helper function (isPoss) verifies if it is possible to pick at least k numbers from the array that are less than or equal to the candidate value while also ensuring the numbers chosen are non-adjacent. When a number qualifies, you skip the next index to enforce the non-adjacency rule.


---


# Approach:
1. Determine Search Boundaries:

- Lower Bound (l): The smallest value in the array (since the capability cannot be less than the smallest number).
- Upper Bound (r): The largest value in the array (since in the worst case, the capability might be the largest number).
2. Binary Search Loop:

- Calculate the mid-value of the current search interval.
- Use the helper function isPoss to check if it’s possible to pick at least k non-adjacent numbers with values ≤ mid.
- If it's possible, update the result to mid and try to find a smaller capability by searching in the lower half.
- If it's not possible, search in the upper half by increasing the lower bound.
3. Greedy Check (isPoss Function):

- Iterate through the array and, whenever you find a number that is ≤ mid, increment a count (representing a valid selection) and skip the next index to maintain non-adjacency.
- If the count reaches k, the function returns true; otherwise, it returns false.
4. Return Result:
- After the binary search completes, the result holds the minimum possible capability.

---

# Time Complexity:
- Binary Search Iterations:
The binary search runs over the range from min(nums) to max(nums), which takes O(log(max - min)) iterations.

- Feasibility Check:
Each binary search iteration calls isPoss, which traverses the array in O(n) time.

- Overall Complexity:
The total time complexity is **O(n * log(max - min))**. This is efficient even for larger arrays as the logarithmic factor generally remains small compared to the linear scan in each iteration.


---
# Space Complexity:
**O(1)**-The binary search solution uses only a constant amount of extra space.

---


# Code
```cpp []
class Solution {
    bool isPoss(vector<int>& nums,int mid,int k){
        int house=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]<=mid){
                house++;
                i++;
            }
        }
        return house>=k;
    }
public:
    int minCapability(vector<int>& nums, int k) {
        int n=nums.size();
        int l=*min_element(begin(nums),end(nums));
        int r=*max_element(begin(nums),end(nums));
        int result=r;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(isPoss(nums,mid,k)){
                result=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return result;
    }
};
```
['C++']