算法导论 练习题 2.3-7

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void merge(int a[],int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int i,j,k;

int *t1=(int*)malloc(sizeof(int)*(n1+1));
int *t2=(int*)malloc(sizeof(int)*(n2+1));

for(i=0;i<n1;i++)
    {
        t1[i]=a[p+i];
    }
    t1[n1]=INT_MAX;

for(i=0;i<n2;i++)
    {
        t2[i]=a[q+1+i];
    }
    t2[n2]=INT_MAX;

    i=j=0;
for(k=p;k<=r;k++)
    {
if(t1[i]<=t2[j])
        {
            a[k]=t1[i];
            i++;
        }
else
        {
            a[k]=t2[j];
            j++;
        }
    }
}

//归并排序
void mergeSort(int a[],int p,int r)
{
if(p<r)
    {
int q=(p+r)/2;
        mergeSort(a,p,q);
        mergeSort(a,q+1,r);
        merge(a,p,q,r);
    }
}

//二分查找有序数组，返回目标值的下标或小于目标值的最大下标
int halfSearch(int a[],int low,int high,int key)
{
int mid=(low+high)/2;
while(a[mid]!=key && a[low]<key && a[high]>key)
    {
        mid=(low+high)/2;
if(a[mid]>key)
        {
            high=mid-1;
        }
else
        {
            low=mid+1;
        }
    }
if(a[mid]==key)
    {
return mid;
    }
if(a[low]>key)
    {
return low-1;
    }
if(a[high]<key)
    {
return high;
    }
}


bool check(int a[],int len,int x)
{
//merge排序耗时nlgn
//for循环耗时上界n，内层halfSearch耗时上界lgn
//总耗时上界nlgn
    mergeSort(a,0,len-1);
int mid=halfSearch(a,0,len-1,x/2);
int iSmall,iBig;
for(iSmall=0;iSmall<=mid;iSmall++)
    {
        iBig=halfSearch(a,iSmall+1,len-1,x-a[iSmall]);
if(a[iSmall]+a[iBig]==x)
return true;
    }
return false;
}


int main()
{
int a[8]={99,4,123,6764,26,324,6,88};
int x=6764+26;
if(check(a,8,x))
    {
printf("Found!");
    }
else
    {
printf("Not Found!");
    }
    getchar();
}