C语言实现分治法求解数组中是否存在两个数之和等于给定目标数的问题

思路：
其实这种解法与遍历每两个数之和有点类似，只不过加了许多小技巧。

首先我们需要对数组排序，然后对数组进行遍历，每次遍历时，在第 i i i个数后面的数 [ i + 1 , . . . , n − 1 ] [i + 1, ..., n - 1] [i+1,...,n−1]中进行对 x − a r r a y [ i ] x-array[i] x−array[i]的二分查找。

总的时间复杂度为 O ( n l o g n + n ∗ n 1 2 ) O(n{log}n + n * n^{frac{1}{2}}) O(nlogn+n∗n21​)。

源代码：

//
//  main.c
//  SumOfTwoNums
//
//  Created by 胡昱 on 2021/11/5.
//

#include 
#include 
#define N 50000

int cmp(const void * a, const void * b) {
    return ( *(int*)a - *(int*)b );
}

int search(int* nums, int numsSize, int target) {
    int low = 0, high = numsSize - 1;
    int mid = (low + high) / 2;
    while (low <= high) {
        mid = (low + high) / 2;
        if(target == nums[mid]) {
            return 1;
        }
        if(target < nums[mid]) {
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return 0;
}

int main(int argc, const char * argv[]) {

    // 共m个问题
    int m;
    scanf("%d", &m);
    while((m--) > 0) {
        // 共n个元素
        int n;
        scanf("%d", &n);
        
        // x为2个元素的和的目标
        int x;
        scanf("%d", &x);
        
        // 创建并输入数组
        int a[N];
        for(int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        
        // 排序，时间复杂度为O(nlogn)
        qsort(a, n, sizeof(int), cmp);
        
        // 查找是否有两个元素和为x
        // 原理为：选出一个数，在剩余的数字里面进行二分查找，故时间复杂度为O(n * n^0.5)
        int flag = search(a + 1, n - 1, x - a[0]);
        for(int i = 1; i < n - 1 && !flag; ++i) {
            // Tip：跳过重复的元素
            if(a[i] == a[i - 1]) {
                continue;
            }
            else {
                flag = search(a + i + 1, n - i, x - a[i]);
            }
        }
        
        // 输出
        if(flag == 1) {
            printf("yesn");
        }
        else {
            printf("non");
        }
    }
    return 0;
}