2.3-7 描述一个运行时间为Θ(nlgn)的算法,给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好为x的元素

时间:2021-09-25 19:53:45
 

描述一个运行时间为Θ(nlgn)的算法,给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好为x的元素

思路:1、将结合S的整数按照从递增的顺序排列得到新的集合S2 2、初始化index1=0 index2=n-1; 3、判断S2[index1]+S2[index2]==x 为真则return true; 为假则继续下一步 4、S2[index1]+S2[index2]<x 为真 index1+1; 为假 index2-1; 5、 如果 index1>index2,返回false