Optimal Binary Search on Answer Solution in C++, JAVA, & PYTHON
Finding Minimum Capability to Select k Elements in an ArrayIn this blog, we'll analyze an efficient solution for determining the minimum capability required to

## **Finding Minimum Capability to Select `k` Elements in an Array**

In this blog, we'll analyze an efficient solution for determining the **minimum capability** required to select `k` elements from an array such that no two selected elements are adjacent. We'll explore the solution in **Java**, **C++**, and **Python**, and understand its logic, time complexity, and practical usage.

---

## **Problem Statement**
Given an array `nums[]` and an integer `k`, your task is to select exactly `k` elements such that:
- **No two selected elements are adjacent**.
- The **maximum value** among the selected elements is **minimized**.

---

## **Approach**
The solution uses **Binary Search** with a **Greedy Checking Function** to efficiently solve the problem.

### **Steps to Solve**
1. **Identify the Search Space:**  
   - The possible values for the minimum capability are between the **minimum** and **maximum** values in the array.  
2. **Binary Search Setup:**  
   - Use `l` as the **minimum** element in the array and `r` as the **maximum** element.  
   - Perform Binary Search to minimize the maximum capability.
3. **Greedy Checking Function:**  
   - For each midpoint value in binary search:
     - Iterate through the array.
     - Track selected elements ensuring no two are adjacent.
     - If we can successfully select `k` elements with a maximum value ≤ `mid`, mark this `mid` as a potential answer.
4. **Update Search Boundaries:**  
   - If the condition holds true, move the right boundary (`r = mid - 1`) to find a smaller possible value.
   - Otherwise, increase the left boundary (`l = mid + 1`).

---

## **Code Implementation**

### **Java Solution**
```java
class Solution {
    public boolean check(int arr[], int val, int k) {
        int count = 0;
        int prev = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= val) {
                if (prev == -1 || prev < i - 1) {
                    prev = i;
                    count++;
                }
            }
        }
        return count >= k;
    }

    public int minCapability(int[] nums, int k) {
        int l = Integer.MAX_VALUE;
        int r = Integer.MIN_VALUE;
        for (int i : nums) {
            l = Math.min(l, i);
            r = Math.max(r, i);
        }
        int ans = r;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(nums, mid, k)) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}
```

---

### **C++ Solution**
```cpp
class Solution {
public:
    bool check(vector<int>& nums, int val, int k) {
        int count = 0, prev = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= val) {
                if (prev == -1 || prev < i - 1) {
                    prev = i;
                    count++;
                }
            }
        }
        return count >= k;
    }

    int minCapability(vector<int>& nums, int k) {
        int l = *min_element(nums.begin(), nums.end());
        int r = *max_element(nums.begin(), nums.end());
        int ans = r;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (check(nums, mid, k)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};
```

---

### **Python Solution**
```python
class Solution:
    def check(self, nums, val, k):
        count, prev = 0, -1
        for i in range(len(nums)):
            if nums[i] <= val:
                if prev == -1 or prev < i - 1:
                    prev = i
                    count += 1
        return count >= k

    def minCapability(self, nums, k):
        l, r = min(nums), max(nums)
        ans = r

        while l <= r:
            mid = (l + r) // 2
            if self.check(nums, mid, k):
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
        return ans
```

---

## **Explanation**
### `check()` Function
- **Logic:** Iterates through the array to find if we can pick `k` non-adjacent elements, all having values less than or equal to `val`.
- Tracks the **last picked index** (`prev`). If the current element satisfies the conditions, it's added to the selection.

### `minCapability()` Function
- Initializes the search space between the **minimum** and **maximum** elements.
- Uses Binary Search to minimize the maximum element in the selected subarray.

---

## **Example Walkthrough**
### Input:
```
nums = [2, 3, 5, 9, 6]
k = 2
```
### Step-by-Step Execution
1. **Search Space:** `l = 2`, `r = 9`
2. **Midpoint Calculation:** `mid = (2 + 9) / 2 = 5`
3. Checking with `val = 5`: Possible to pick `2` elements → **Valid**
   - Update `ans = 5`, `r = 4`.
4. **New Midpoint:** `mid = 3`
5. Checking with `val = 3`: Not possible to pick `2` elements → **Invalid**
   - Update `l = 4`.
6. **New Midpoint:** `mid = 4`
7. Checking with `val = 4`: Not possible → **Invalid**
   - Update `l = 5`.

**Final Answer:** `5`

---

## **Complexity Analysis**
- **Time Complexity:** `O(n log m)`  
  - `n` = size of the array  
  - `m` = range of values in the array (max - min)  
- **Space Complexity:** `O(1)` (In-place calculations)

---

## **Key Takeaways**
✅ Efficient use of **Binary Search** reduces the time complexity.  
✅ The **Greedy Approach** in the `check()` function efficiently checks conditions for valid element selection.  
✅ The algorithm effectively balances **minimizing the maximum value** while ensuring **`k` non-adjacent elements** are chosen.

---

## **Practice Problems for Mastery**
To deepen your understanding, try these problems:
- [Leetcode 2402: Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/)
- [Leetcode 300: Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)
- [Leetcode 410: Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/)

---

If you have any questions or would like further explanation, feel free to ask! 🚀
['Array', 'Binary Search', 'Python', 'C++', 'Java', 'Python3']