50、面试高频题（三）：二分查找变种、Top K问题、括号匹配、设计一个内存池

好，咱们今天聊几个面试里特别爱考的硬骨头。说实话，这些题不光面试有用，实际项目里也经常碰到。我个人习惯是把它们归为一类——「看着简单，一写就错」。你想想看，二分查找谁不会？但变种一来，边界条件就让人头大。Top K 问题，堆排还是快排？括号匹配，栈的经典应用。内存池设计，嗯，这个才是真正考验功底的地方。

咱们一个一个来拆。

一、二分查找变种：不只是找中间值

标准的二分查找，大家都会。但面试官不会只考这个。他们喜欢问：「找第一个等于 target 的位置」、「找最后一个等于 target 的位置」、「找第一个大于等于 target 的位置」。

我在项目中遇到过这样一个场景：一个有序的日志时间戳数组，需要找到某一天的第一条日志。用标准二分查找？不行，因为可能有多个相同的时间戳。这时候就需要变种。

举个例子，找第一个等于 target 的位置：

int findFirst(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // 继续向左找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

注意看，当 arr[mid] == target 时，我们不直接返回，而是把 right 移到 mid - 1，继续向左搜索。这样就能找到最左边那个。

类似的，找最后一个等于 target 的位置，就把 left = mid + 1 继续向右搜。找第一个大于等于 target 的位置，判断条件改成 arr[mid] >= target 时收缩右边界。

说白了，这些变种就是在标准二分查找的框架下，微调「相等时的处理逻辑」。你只要记住：找最左就右移右边界，找最右就左移左边界。

二、Top K 问题：堆排还是快排？

Top K 问题，面试里出现频率极高。给你一个无序数组，找出最大的 K 个数。或者最小的 K 个数。

常见的解法有两种：

• 堆排序法：维护一个大小为 K 的小顶堆（找最大 K 个）或大顶堆（找最小 K 个）。时间复杂度 O(N log K)。
• 快速选择法：基于快排的 partition 思想，每次把数组分成两部分，直到找到第 K 大的位置。平均时间复杂度 O(N)，最坏 O(N²)。

我个人习惯是：数据量不大时用堆，简单稳定；数据量很大时用快速选择，效率更高。但要注意，快速选择会修改原数组，如果要求不能修改，那就只能用堆。

来看堆的代码实现：

// 找最大的 K 个数，用小顶堆
void topKByHeap(int arr[], int n, int k) {
    // 建一个大小为 k 的小顶堆
    int* heap = (int*)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        heap[i] = arr[i];
    }
    // 建堆
    for (int i = k/2 - 1; i >= 0; i--) {
        heapify(heap, k, i);
    }
    // 遍历剩余元素
    for (int i = k; i < n; i++) {
        if (arr[i] > heap[0]) {
            heap[0] = arr[i];
            heapify(heap, k, 0);
        }
    }
    // 此时 heap 中就是最大的 K 个数
}

快速选择法呢？其实就是快排的 partition 过程。每次选一个 pivot，把比它大的放左边，比它小的放右边。如果 pivot 的位置正好是 K-1，那左边就是 Top K。如果位置大于 K-1，就在左边继续找；小于 K-1，就在右边找。

嗯，这里要注意：快速选择的最坏情况是 O(N²)，但实际中很少出现。如果面试官追问，你可以说「可以用随机选择 pivot 来避免最坏情况」。

三、括号匹配：栈的经典应用

括号匹配，说白了就是检查一个字符串里的括号是否成对出现、顺序是否正确。比如 () 合法，(] 不合法，([)] 也不合法。

解法很简单：遇到左括号就入栈，遇到右括号就检查栈顶是否匹配。匹配就弹出，不匹配就返回 false。最后栈为空才合法。

代码实现：

bool isValid(char* s) {
    int len = strlen(s);
    char* stack = (char*)malloc(len * sizeof(char));
    int top = -1;
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            stack[++top] = s[i];
        } else {
            if (top == -1) return false;  // 栈空，无匹配
            char left = stack[top--];
            if ((s[i] == ')' && left != '(') ||
                (s[i] == ']' && left != '[') ||
                (s[i] == '}' && left != '{')) {
                return false;
            }
        }
    }
    return top == -1;
}

这个题还有变种，比如要求同时支持多种括号，或者要求输出匹配的位置。但核心思想不变——栈是解决括号匹配问题的天然工具。

四、设计一个内存池

这个题有点意思。面试官让你设计一个内存池，说白了就是预先分配一大块内存，然后自己管理分配和释放。为什么要这么做？因为频繁调用 malloc/free 有性能开销，而且容易产生内存碎片。

我参与过一个嵌入式项目，内存只有 64KB，用标准 malloc 根本不行。后来我们自己写了个内存池，固定分配 16 字节的块，效率高多了。

一个简单的内存池设计：

• 预分配：一次性申请一大块连续内存。
• 分块管理：把内存分成固定大小的块，用链表或位图管理空闲块。
• 分配：从空闲链表中取一个块返回。
• 释放：把块放回空闲链表。

来看一个最简单的实现：

#define BLOCK_SIZE 64
#define BLOCK_NUM  1024

typedef struct MemPool {
    char pool[BLOCK_SIZE * BLOCK_NUM];
    int free_list[BLOCK_NUM];  // 空闲块索引栈
    int free_count;
} MemPool;

void pool_init(MemPool* mp) {
    mp->free_count = BLOCK_NUM;
    for (int i = 0; i < BLOCK_NUM; i++) {
        mp->free_list[i] = i;
    }
}

void* pool_alloc(MemPool* mp) {
    if (mp->free_count == 0) return NULL;
    int idx = mp->free_list[--mp->free_count];
    return mp->pool + idx * BLOCK_SIZE;
}

void pool_free(MemPool* mp, void* ptr) {
    int idx = ((char*)ptr - mp->pool) / BLOCK_SIZE;
    mp->free_list[mp->free_count++] = idx;
}

面试时，你还可以提一下内存池的优缺点：

优点	缺点
分配/释放速度快（O(1)）	内存利用率可能不高（内部碎片）
无内存碎片	只适合固定大小分配
适合实时系统	实现复杂度比 malloc 高

嗯，这里要注意：面试官可能会追问「如果内存池用完了怎么办？」你可以回答「可以设计一个扩容机制，或者返回错误码让上层处理」。

最后，我用一张图来总结这四个知识点的关系：

这四个题，表面上看是算法题，实际上考察的是对基础数据结构和边界条件的理解。二分查找考的是边界处理，Top K 考的是堆和快排的灵活运用，括号匹配考的是栈，内存池考的是内存管理。你把这些吃透了，面试基本稳了。

---

公众号:蓝海资料掘金营，微信deep3321