輸入一個數組和一個數字，在數組中查找兩個數，使得它們的和正好是輸入的那個數字 時間複雜度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;
}