【编程】判断一个存有递增数列的数组中，是否存在两个数的和等于给定的数字k

时间复杂度O(nlogn) 优于O(N^2)
#include <stdio.h>
#include <stdlib.h>
#define SUM_OK1
#define SUM_FAIL0
typedef struct _Pair{
int a;
int b;
}Pair;
static Pair ret;
int sum_binary_search( int * datas, int start, int len, int match )
{
int low =-1;
int pos = -1;
//为了便于测试 固定len是10 然后以下数据也都可以先写死进去
if (datas[7]<match) low = 10-8;
//assert(datas[low]<match && datas[low+8]>=match)
if (datas[low+4]<match) low += 4;
//assert(datas[low]<match && datas[low+4]>=match)
if (datas[low+2]<match) low += 2;
//assert(datas[low]<match && datas[low+2]>=match)
if (datas[low+1]<match) low += 1;
//assert(datas[low]<match && datas[low+1]>=match)
pos = low+1;
if (pos>10 || datas[pos]!=match)
{
pos = -1;
}
else{
ret.b = datas[pos];
}
return pos;
}
int search_pair( int * datas, int sum, int len )
{
int i;
int retVal = SUM_FAIL;
int *pair_datas = (int*)calloc(len,sizeof(int));
for (i = 0;i<len;i++)
pair_datas[i] = sum -datas[i];
for (i = 0;i<len;i++) //O(n)
{
ret.a = sum - pair_datas[i];
if (-1 != sum_binary_search(datas,0,len,pair_datas[i])) //O(lgn)
{
retVal = SUM_OK;
printf("(%d,%d)\n",ret.a,ret.b);
break;//----------要想打印出所有合适的结果去掉这个break即可 你自己使用入参来控制即可
}
} //-----> O(nlgn)
free(pair_datas);
pair_datas = NULL;
return retVal;
}
int compare(const void* a,const void* b){
int* t = (int*)a;int* s = (int*)b;
return (*t-*s);
}
int main(){
int (*cmp)(const void*,const void*) = compare;
int datas[10] = {2,10,5,3,4,6,13,7,11,9};
int sum = 13;
int len = 10;
qsort(datas,len,sizeof(int),cmp);
search_pair(datas,sum,len);
return EXIT_SUCCESS;
}追问

感谢帮忙，对C语言我不是非常了解，在search_pair中有一个calloc似乎没有定义就可以使用，是stdlib.h中的吗？做什么用的呢？还有好像search_pair并没有用到递归？

追答

在stdlib.h中 用于分配一块区域，并且将该块区域初始化为0，没看到递归的说明，所以确实没用到

温馨提示：答案为网友推荐，仅供参考

当前网址：https://verywind.cn/ee/yeje372fv.html