题目是：描述一个运行时间为Θ（nlgn）的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素

思路：首先对该数组进行排序，因为运行时间O(nlgn)我选择了归并排序。归并排序的合并函数在《算法导论练习2.3-2和2.3-3》中有提到。然后排序的时候利用递归就可以实现了。源码会在下面展示出来。

对于程序的后半部分查找求和。有两种思路，一种是利用二分查找去实现。二分查找也是O(nlgn)的复杂度，所以符合本题的条件。但是我用的是从两端向里进行求和，最坏的情况下也是O(n)的复杂度，比二分查找更快一些。以下是源码。

#include <stdio.h>
//#include "mergeSort.h"
//#include "merge.h"

void myMerge(int arr[], int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int left[n1];
    int right[n2];

    for (int i = 0; i < n1; i++)
    {
        left[i] = arr[i + p - 1];
    }
    for (int j = 0; j < n2; j++)
    {
        right[j] = arr[j + q];
    }

    int i = 0;
    int j = 0;
    int k = p - 1;
    while (i != n1 && j != n2)
    {
        if (left[i] < right[j])
        {
            arr[k] = left[i];
            i++;
        }
        else
        {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    if (i == n1)
    {
        while (j < n2)
        {
            arr[k] = right[j];
            j++;
            k++;
        }
    }
    else
    {
        while (i < n1)
        {
            arr[k] = left[i];
            i++;
            k++;
        }
    }
}

void myMergeSort(int arr[], int start, int end)
{
    if (start < end)
    {
        int middle = (start + end) / 2;
        myMergeSort(arr, start, middle);
        myMergeSort(arr, middle + 1, end);
        myMerge(arr, start, middle, end);
    }
}

int main()
{
    int arr[10] = {1, 2, 4, 5, 32, 5, 3, 5, 4, 2};
    //进行归并排序 O(nlgn)
    myMergeSort(arr, 1, 10);
    //进行从两端向中间求和并寻找 最坏情况下的复杂度 O(n)

    int i = 0;
    int j = 9;
    while (i < j)
    {
        if (arr[i] + arr[j] == 37)
        {
            printf("存在两个数和37，这两个数为%d和%d", arr[i], arr[j]);
            return 1;
        }
        if (arr[i] + arr[j] < 37)
        {
            i++;
        }
        if (arr[i] + arr[j] > 37)
        {
            j--;
        }
    }
    printf("不存在两个数和37。");
    return 0;
}