有序数组公共元素查找：循环+二分查找的最坏时间复杂度是否符合O(N)要求

首先直接说结论：你当前的实现达不到题目要求的最坏情况O(N)时间复杂度，咱们来一步步拆解原因，再给出符合要求的解法。

为什么当前方法的时间复杂度是O(N log N)？ #

你现在的思路是遍历数组a的每个元素（这一步是O(N)），然后对每个元素在数组b中执行二分查找——而二分查找的时间复杂度是O(log N)，所以整体时间复杂度是O(N * log N)，这比题目要求的**线性时间O(N)**要高，不符合"最坏情况下执行时间与N成正比"的要求。

符合O(N)时间复杂度的正确思路：双指针法 #

因为两个数组都是有序的，我们可以用双指针同步遍历两个数组，全程只需要一次线性遍历，时间复杂度就是O(N)：

• 初始化两个指针i（指向数组a的起始位置）和j（指向数组b的起始位置）
• 比较a[i]和b[j]：
  • 如果a[i] == b[j]，这就是公共元素，记录下来，同时移动两个指针i++、j++
  • 如果a[i] < b[j]，说明a当前元素更小，不可能在b的后续位置找到它，移动i++
  • 如果a[i] > b[j]，同理移动j++
• 直到其中一个指针超出数组长度，遍历结束

代码实现对比 #

你的原代码（用于参考） #

#include <stdio.h>

int binary_search(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key < a[mid])
            high = mid - 1;
        else if (key > a[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

int main() {
    int a[6] = {2, 8, 15, 31, 46, 75};
    int b[6] = {1, 8, 17, 21, 31, 75};
    int i, tam = 6, key, res, c[6], k=0;
    for (i = 0; i < tam; i++) {
        key = a[i];
        res = binary_search(b, tam, key);
        if (res != -1) {
            c[k] = a[i];
            k++;
        }
    }
    // 输出公共元素
    for(i=0; i<k; i++){
        printf("%d ", c[i]);
    }
    return 0;
}

优化后的双指针法代码 #

#include <stdio.h>

int main() {
    int a[6] = {2, 8, 15, 31, 46, 75};
    int b[6] = {1, 8, 17, 21, 31, 75};
    int i = 0, j = 0, tam = 6, c[6], k = 0;
    
    while (i < tam && j < tam) {
        if (a[i] == b[j]) {
            c[k++] = a[i];
            i++;
            j++;
        } else if (a[i] < b[j]) {
            i++;
        } else {
            j++;
        }
    }
    
    // 输出公共元素
    for (int idx = 0; idx < k; idx++) {
        printf("%d ", c[idx]);
    }
    return 0;
}

时间复杂度验证 #

双指针法中，每个指针最多移动N次，总共移动次数不超过2N，所以最坏情况下时间复杂度是O(N)，完全符合题目要求。

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