输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字 时间复杂度O(NlogN)

/*
*[email protected] 转载请注明出处
*题目：输入一个数组和一个数字，在数组中查找两个数，
*使得它们的和正好是输入的那个数字。
*如果有多对数字的和等于输入的数字，输出任意一对即可。
*例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
*数组有序的情况，二分查找法，
*题目相当于，对每个a[i]，然后查找判断sum-a[i]是否也在原始序列中，对于每个a[i]，
*二分查找sum-a[i]是否在原始序列中
*时间复杂度O(NlogN)   空间复杂度O(1)
*/

#include <cstdio>

int binarySearch(int *array,int len,int a)
{
    int low = 0;
    int high = len - 1;
    int mid = 0;
    while(low <= high)
    {
        mid = (low + high)/2;
        if(array[mid] == a)
            return 1;
        else
        {
            if(array[mid] < a)
                low = mid + 1;
            else
                high = mid - 1;
        }
    }
    return 0;
}

int findConditionedNum(int &num1,int &num2,int *array,int len,int sum)
{
    for(int i = 0;i < len;++i)
    {
        int a = sum - array[i];
        int flag = binarySearch(array,len,a);
        if(flag == 1)
        {
            num1 = array[i];
            num2 = a;
            return 1;
        }
    }
    return 0;
}

int main()
{
    int array[] = {1,2,4,7,11,15};
    int sum = 15;
    int num1 = 0;
    int num2 = 0;
    int a = findConditionedNum(num1,num2,array,sizeof(array)/sizeof(int),sum);
    printf("%d  %d  %d\n",a,num1,num2);
    getchar();
    return 0;
}