如何优化自定义二分搜索C++代码以降低内存占用并将运行时间控制在2秒以内？

Hey there! Let's walk through fixing the timeout and memory issues in your code. The main problems are inefficient query handling and slow input processing—here's how to fix them:

1. Replace Linear Scans with Proper Binary Search for l and r #

Your current code uses linear while loops to find l and r for each query, which is O(n) per query. With 300,000 queries, this leads to an O(kn) time complexity (9e10 operations!)—way too slow. Instead, we need to implement lower_bound and upper_bound using binary search, both of which run in O(log n) per query.

• lower_bound(x): Finds the first index where element ≥ x
• upper_bound(x): Finds the first index where element > x
• To check if x exists (b), just verify if lower_bound(x) is within the array bounds and the element at that index equals x.

Here's the implementation for these functions:

template <typename T>
int lower_bound(const vector<T>& arr, T x) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

template <typename T>
int upper_bound(const vector<T>& arr, T x) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] <= x) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

2. Optimize Input Handling for Speed & Reduced Memory #

Your current string-splitting and conversion code is slow and uses unnecessary memory. Instead, use cin directly with synchronization disabled to speed up input operations—this eliminates the need for string processing entirely.

Add these lines at the start of main() to boost cin speed:

ios::sync_with_stdio(false);
cin.tie(nullptr);

Then read input directly without string manipulation:

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
        int x;
        cin >> x;
        int l = lower_bound(arr, x);
        int r = upper_bound(arr, x);
        int b = (l < n && arr[l] == x) ? 1 : 0;
        cout << b << " " << l << " " << r << "\n";
    }

    return 0;
}

This cuts out all the string vectors and conversion overhead, saving memory and making input reading much faster.

3. Remove Unnecessary Code #

Your original binary_search function is redundant now—we can determine if x exists using the lower_bound result directly. Removing it simplifies the code and reduces memory usage slightly.

4. Key Notes on Correctness #

• We use high = arr.size() (not arr.size() - 1) in the binary search functions to handle cases where all elements are smaller than x (returning n as required).
• The calculation mid = low + (high - low) / 2 avoids integer overflow, which is crucial for large array sizes up to 3e5.
• We use cout << "\n" instead of endl to avoid unnecessary buffer flushes, which also speeds up output.

Final Optimized Code #

Putting it all together, here's the full optimized code:

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

template <typename T>
int lower_bound(const vector<T>& arr, T x) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

template <typename T>
int upper_bound(const vector<T>& arr, T x) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] <= x) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    int k;
    cin >> k;
    while (k--) {
        int x;
        cin >> x;
        int l = lower_bound(arr, x);
        int r = upper_bound(arr, x);
        int b = (l < n && arr[l] == x) ? 1 : 0;
        cout << b << " " << l << " " << r << "\n";
    }

    return 0;
}

This code will handle the maximum input sizes easily within the 2-second time limit, with minimal memory usage.

内容的提问来源于stack exchange，提问作者Emily Grace Seville