如何高效查找含范围与单个值的uint32_t数组的最大最小值

Great question! Let's walk through how to optimize finding the min and max for this specific array structure—plus fix a subtle bug in your current implementation.

First off, let's confirm the array structure we're working with:

• The first element (arr[0]) tells us how many range pairs exist. Each range uses two consecutive elements (e.g., arr[1] & arr[2] form one range, arr[3] & arr[4] form another, etc.).
• Any elements after these range pairs are standalone single values.

The Bug in Your Current Code #

Your current implementation has a critical issue when there are 0 ranges (like arr3 where arr[0] = 0):

max = arr1[1]; min = arr1[1]; // For arr3, this initializes to 14, but the actual min is 5!

When there are no ranges, all elements starting at index 1 are single values—but your code locks in arr[1] as the initial min/max, which misses smaller/larger values later in the array.

A More Efficient & Correct Approach #

We can optimize by leveraging the array's structure to reduce redundant checks, and fix the initialization logic to handle all edge cases:

1. Initialize min/max correctly: Start with the first data element (index 1), since even if there are 0 ranges, this is the first value we need to compare.
2. Process range pairs smartly: For each range, we only need to find the min and max of the two elements once, then update our global min/max. No need to check each element against the global values separately.
3. Cleanly handle single values: After processing all ranges, iterate through the remaining elements and update our min/max as needed.

Working Code Implementation

#include <stdint.h>
#include <stddef.h>
#include <limits.h>

void find_min_max(const uint32_t* arr, size_t arr_len, uint32_t* out_min, uint32_t* out_max) {
    // Edge case: array only has the count element (no data)
    if (arr_len <= 1) {
        *out_min = UINT32_MAX;
        *out_max = UINT32_MIN;
        return;
    }

    // Initialize with the first data element
    *out_min = arr[1];
    *out_max = arr[1];

    size_t num_ranges = arr[0];
    size_t range_end_idx = 1 + 2 * num_ranges; // Index after the last range element

    // Process each range pair
    for (size_t i = 1; i < range_end_idx; i += 2) {
        uint32_t val1 = arr[i];
        uint32_t val2 = arr[i + 1];
        
        // Get min/max of the current range
        uint32_t range_min = (val1 < val2) ? val1 : val2;
        uint32_t range_max = (val1 > val2) ? val1 : val2;

        // Update global min/max
        if (range_min < *out_min) *out_min = range_min;
        if (range_max > *out_max) *out_max = range_max;
    }

    // Process remaining single values
    for (size_t i = range_end_idx; i < arr_len; i++) {
        if (arr[i] < *out_min) *out_min = arr[i];
        if (arr[i] > *out_max) *out_max = arr[i];
    }
}

Why This Is Better #

• Fixes the edge case bug: When there are 0 ranges, the range loop doesn't run, and we process all elements from index 1 onward as single values—so we'll catch the real min/max.
• Minimal redundant comparisons: For ranges, we compare the two elements once to get the range's min/max, then only do two checks against the global values (instead of four if we checked each element separately).
• Type-safe & idiomatic: Using size_t for indices matches the return type of sizeof, which is standard practice in C.

Testing with Your Examples #

Let's verify this works with your test cases:

• arr1 = {2, 34, 78, 5, 10, 100}:
  • Ranges: (34,78) → min 34, max 78; (5,10) → min 5, max10. Global min becomes 5, max becomes78.
  • Single value: 100 → max updates to 100. Final result: min=5, max=100.
• arr2 = {1, 18, 39, 2}:
  • Range: (18,39) → min18, max39. Global min=18, max=39.
  • Single value:2 → min updates to2. Final result: min=2, max=39.
• arr3 = {0,14,5,256,99}:
  • No ranges, process all elements from index1: 14 → 5 (min becomes5) →256 (max becomes256) →99. Final result: min=5, max=256.

All cases work perfectly, and the code runs efficiently with no wasted operations.

内容的提问来源于stack exchange，提问作者pavikirthi