如何用二分查找获取特定结构数组的最大值（C语言）

嘿，这个需求很明确，咱们可以用二分查找来搞定O(log n)的时间复杂度，毕竟数组的结构是前半段非递减的非零元素，后半段全是0，天生就适合二分法来定位边界。

核心思路 #

我们的目标是找到数组中第一个出现的0的位置：

• 如果第一个0的位置是0，说明整个数组都是0，直接返回0；
• 如果第一个0的位置是n（超出数组范围），说明数组里没有0，返回最后一个元素；
• 其他情况，第一个0的前一个位置就是最后一个非零元素，返回它的值就行。

为什么用这个思路？因为二分查找找边界的时间复杂度正好是O(log n)，完美符合要求。

代码实现 #

#include <stdio.h>

int findMax(int a[], int n) {
    if (n == 0) {
        return 0; // 处理空数组的情况
    }
    
    int left = 0;
    int right = n; // right初始化为n，覆盖数组无0的情况
    
    while (left < right) {
        int mid = left + (right - left) / 2; // 避免left+right溢出
        if (a[mid] == 0) {
            right = mid; // 第一个0在mid左边，缩小右边界
        } else {
            left = mid + 1; // 第一个0在mid右边，缩小左边界
        }
    }
    
    if (left == 0) {
        return 0; // 全0数组
    } else {
        return a[left - 1];
    }
}

// 测试用例
int main() {
    int arr1[] = {1,5,5,7,8,0,0,0};
    printf("Test 1: %d\n", findMax(arr1, 8)); // 输出8
    
    int arr2[] = {2,4,5,6,6,8,9,9};
    printf("Test 2: %d\n", findMax(arr2, 8)); // 输出9
    
    int arr3[] = {0,0,0};
    printf("Test 3: %d\n", findMax(arr3, 3)); // 输出0
    
    int arr4[] = {5};
    printf("Test 4: %d\n", findMax(arr4, 1)); // 输出5
    
    int arr5[] = {0};
    printf("Test 5: %d\n", findMax(arr5, 1)); // 输出0
    
    return 0;
}

关键细节解释 #

• 边界处理：right初始化为n而不是n-1，是为了处理数组中没有0的情况（比如第二个测试用例），此时循环结束后left会等于n，我们直接取a[left-1]也就是最后一个元素。
• 避免溢出：计算mid时用left + (right - left)/2而不是(left+right)/2，防止当left和right都是很大的整数时相加溢出。
• 全0数组判断：当left最终等于0时，说明从第一个元素开始就是0，直接返回0即可。

这样写出来的函数完全符合O(log n)的时间复杂度要求，而且覆盖了所有可能的边界情况。

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