Binary Search Applications in Fractional Programming

Consider an optimization problem where we seek the maximum average value over subarrays of minimum length. Given array elements $a_1, a_2, ..., a_n$ and minimum length constraint $L$, we want to find:

$$\max_{\substack{1 \leq i \leq j \leq n \ j - i + 1 \geq L}} \frac{\sum_{k=i}^{j} a_k}{j - i + 1}$$

Let's denote the optimal solution as $X^{*}$. This means there exist indices $i, j$ such that:

$$\max_{\substack{1 \leq i \leq j \leq n \ j - i + 1 \geq L}} \left(\frac{\sum_{k=i}^{j} a_k}{j - i + 1}\right) = X^{*}$$

This can be transformed into finding when:

$$\max_{\substack{1 \leq i \leq j \leq n \ j - i + 1 \geq L}} \left(\sum_{k=i}^{j} a_k - X^{*}\right) = 0$$

Mathematical Foundation

For the optimal value $X^{*}$, every valid subarray satisfies:

$$\frac{\sum_{k=i}^{j} a_k}{j - i + 1} \leq X^{*}$$

Rearranging gives:

$$\sum_{k=i}^{j} a_k \leq X^{*}(j - i + 1)$$

Which becomes:

$$\sum_{k=i}^{j} (a_k - X^{*}) \leq 0$$

Since the optimal subarray achieves equality:

$$\sum_{k=i^{}}^{j^{}} (a_k - X^{*}) = 0$$

Therefore:

$$\max_{\substack{1 \leq i \leq j \leq n \ j - i + 1 \geq L}} \left(\sum_{k=i}^{j} (a_k - X^{*})\right) = 0$$

Monotonicity Property

Define function $H(X)$ as:

$$H(X) = \max_{\substack{1 \leq i \leq j \leq n \ j - i + 1 \geq L}} \left(\sum_{k=i}^{j} (a_k - X)\right)$$

The function $H(X)$ exhibits monotonic behavior: for any $X_1 < X_2$, we have $H(X_1) > H(X_2)$.

This monotonic property enables binary search to locate the value where $H(X) = 0$.

When $H(X) < 0$, we need larger $X$ values; when $H(X) > 0$, we need smaller $X$ values.

Efficient Computation Strategy

For a fixed value $M$, we need to compute:

$$H(M) = \max_{\substack{1 \leq i \leq j \leq n \ j - i + 1 \geq L}} \left(\sum_{k=i}^{j} (a_k - M)\right)$$

Let $c_i = a_i - M$. We transform this into finding maximum subarray sum with length constraints.

Without Length Constraint

Without the length constraint, the problem becomes:

$$F(M) = \max_{1 \leq i \leq j \leq n} \left(\sum_{k=i}^{j} c_k\right) = \max_{1 \leq j \leq n} \left(\sum_{k=1}^{j} c_k - \min_{1 \leq i < j} \sum_{l=1}^{i} c_l\right)$$

Define $prefixSum(x) = \sum_{i=1}^{x} c_i$ and $minPrefix(x) = \min_{1 \leq i \leq x} prefixSum(i)$.

The relationship holds: $minPrefix(x+1) = \min(minPrefix(x), prefixSum(x+1))$.

Implementation approach:

long double prefixSum = 0, minPrefix = 0, result = -1e18;
for (int idx = 1; idx <= n; idx++) {
    prefixSum += transformedArray[idx];
    result = max(result, prefixSum - minPrefix);
    minPrefix = min(minPrefix, prefixSum);
}

With Length Constraint

With the constraint $j - i + 1 \geq L$, the formula transforms to:

$$H(M) = \max_{1 \leq j \leq n} \left(\sum_{k=1}^{j} c_k - \min_{1 \leq i \leq j-L} \sum_{l=1}^{i} c_l\right)$$

This means $H(M) = \max_{1 \leq j \leq n} (prefixSum[j] - minPrefix[j-L])$.

Implementation with constraint:

vector<long double> prefixSum(n + 1, 0);
long double result = -1e18;
long double currentMin = 1e18;

for (int idx = 1; idx <= n; idx++) {
    prefixSum[idx] = prefixSum[idx - 1] + (originalArray[idx] - midValue);
    
    if (idx >= minLength) {
        result = max(result, prefixSum[idx] - currentMin);
    }
    
    if (idx >= minLength) {
        currentMin = min(currentMin, prefixSum[idx - minLength + 1]);
    }
}

Alternative early termination approach:

bool checkCondition(long double threshold) {
    vector<long double> prefixSum(n + 1, 0);
    long double currentMin = 1e18;
    
    for (int idx = 1; idx <= n; idx++) {
        prefixSum[idx] = prefixSum[idx - 1] + (originalArray[idx] - threshold);
        
        if (idx >= minLength) {
            if (prefixSum[idx] - currentMin >= 0) {
                return true;
            }
        }
        
        if (idx >= minLength) {
            currentMin = min(currentMin, prefixSum[idx - minLength + 1]);
        }
    }
    return false;
}

This optimization works because if any subarray produces a non-negative result, the optimal solution will also be non-negative, allowing us to increase our search parameter.