【求解一题java面试题】，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，

Question

5.对于一个已经排好序的数组a，给定一个数X，判断该数组中是否存在2个数的和等于X
  要求时间复杂度为0（n）;
题目是搜下来的。不给代码也行，最好给思路

Answer 1

0(n)，也就是要求一次遍历，整体算法是：两头定位，然后双头向中间进行搜索。因为是排序好的，假定是升序好了，也就是左小右大。1、从左右两端开始，比如 pLeft = 0 和 pRight = length-1
2、如果：v[pLeft] + v[pRight] > X，那么要缩小，也即pRight--；
3、如果：v[pLeft] + v[pRight] < X，那么要增大，也即pLeft++；
4、重复2、3直到命中或pLeft == pRight，这就失败了。其它优化可以考虑快速失败的情况，比如：v[pLeft]>X，明显绝对不可能命中的了。