#include <iostream>
#include <vector>
using namespace std;

// Classic binary search
int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Not found
}

// Lower bound: first position where element >= target
int lowerBound(vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

// Upper bound: first position where element > target
int upperBound(vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

int main() {
    vector<int> arr = {1, 2, 2, 2, 3, 4, 5, 6, 7, 8};
    
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    int target = 2;
    cout << "Target: " << target << endl;
    cout << "Binary search result: " << binarySearch(arr, target) << endl;
    cout << "Lower bound: " << lowerBound(arr, target) << endl;
    cout << "Upper bound: " << upperBound(arr, target) << endl;
    cout << "Count of target: " << (upperBound(arr, target) - lowerBound(arr, target)) << endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Check if we can split array into k subarrays with max sum <= maxSum
bool canSplit(vector<int>& arr, int k, long long maxSum) {
    int subarrays = 1;
    long long currentSum = 0;
    
    for (int num : arr) {
        if (num > maxSum) return false;
        
        if (currentSum + num <= maxSum) {
            currentSum += num;
        } else {
            subarrays++;
            currentSum = num;
            if (subarrays > k) return false;
        }
    }
    
    return true;
}

long long splitArray(vector<int>& arr, int k) {
    long long left = *max_element(arr.begin(), arr.end());
    long long right = 0;
    
    for (int num : arr) {
        right += num;
    }
    
    while (left < right) {
        long long mid = left + (right - left) / 2;
        
        if (canSplit(arr, k, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    vector<int> arr = {7, 2, 5, 10, 8};
    int k = 2;
    
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    cout << "Split into " << k << " subarrays" << endl;
    cout << "Minimum possible maximum sum: " << splitArray(arr, k) << endl;
    
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;

// Example function: f(x) = -(x-3)^2 + 10 (has maximum at x=3)
double f(double x) {
    return -(x - 3) * (x - 3) + 10;
}

// Ternary search for maximum
double ternarySearchMax(double left, double right, double eps = 1e-9) {
    while (right - left > eps) {
        double m1 = left + (right - left) / 3;
        double m2 = right - (right - left) / 3;
        
        if (f(m1) < f(m2)) {
            left = m1;
        } else {
            right = m2;
        }
    }
    
    return (left + right) / 2;
}

// Ternary search for minimum
double ternarySearchMin(double left, double right, double eps = 1e-9) {
    while (right - left > eps) {
        double m1 = left + (right - left) / 3;
        double m2 = right - (right - left) / 3;
        
        if (f(m1) > f(m2)) {
            left = m1;
        } else {
            right = m2;
        }
    }
    
    return (left + right) / 2;
}

// Discrete ternary search
int ternarySearchMaxDiscrete(int left, int right) {
    while (right - left > 2) {
        int m1 = left + (right - left) / 3;
        int m2 = right - (right - left) / 3;
        
        if (f(m1) < f(m2)) {
            left = m1;
        } else {
            right = m2;
        }
    }
    
    // Check remaining candidates
    double maxVal = f(left);
    int result = left;
    
    for (int i = left + 1; i <= right; i++) {
        if (f(i) > maxVal) {
            maxVal = f(i);
            result = i;
        }
    }
    
    return result;
}

int main() {
    double left = 0, right = 6;
    
    cout << "Function: f(x) = -(x-3)^2 + 10" << endl;
    cout << "Search range: [" << left << ", " << right << "]" << endl;
    
    double maxPoint = ternarySearchMax(left, right);
    cout << "Maximum at x = " << maxPoint << endl;
    cout << "f(" << maxPoint << ") = " << f(maxPoint) << endl;
    
    // Discrete version
    int discreteMax = ternarySearchMaxDiscrete(0, 6);
    cout << "Discrete maximum at x = " << discreteMax << endl;
    cout << "f(" << discreteMax << ") = " << f(discreteMax) << endl;
    
    return 0;
}