【剑指offer-解题系列（43）】和为S的两个数

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

对应每个测试案例，输出两个数，小的先输出。 分析 遍历数组查找一个数，然后使用upper查找另一个书所在的位置 代码实现     vector<int> FindNumbersWithSum(vector<int> array,int sum) {         vector<int>res;         if(array.size()<=0)             return res;         int mul = INT_MAX;         int last_a;         int last_b;         int count=0;         for(auto it = array.begin();it!=array.end();it++){         int a =*it;             int b =sum-a;             if(-1!= upper( array , b ,  0, array.size())){                 count++;                 if(a*b<mul){                     mul=a*b;                     last_a=a;                     last_b=b;                 }             }         }         if(count>0){             res.push_back(last_a);             res.push_back(last_b);         }         return res;     }          int upper(vector<int> &data ,int k,  int start, int end){         if(start == end ){             if(data[end] == k)return end;             else return -1;         }         int mid =  (start + end)/2;         if( data[mid] >  k  )return upper( data ,  k ,   start,   mid);         if( data[mid] <  k  )return upper( data ,  k ,   mid+1,   end);         if( data[mid] ==  k  ){             if( mid<end&&data[mid+1]!=k  )                 return mid;             else                 return upper( data ,  k ,   mid+1,   end);         }         return -1; }