[算法题]求数组交加

[算法题]求数组交集

有两个长度分别为m,n的升序整型数组，其中n>m*m,求这两个数组的交集，要求复杂度尽可能低。

如数组a:-1,4,5
数组b:-15，1，3，4，5，7，8，9，10，15
结果应该是：4，5
带不带猜的，假定长数组中目标数平均分布且恰好为最后一个，那就只需要短数组与长数组划分之后的最后一个数字比较。以上纯属YY。
------解决方案--------------------
顺序遍历，O(m)。
平方的条件没用上。
------解决方案--------------------
因为题目说 n>m*m，也就意味着 m 数组比较少，而 n 数组巨大；这个应该是关注点。

所以考虑以 m数组 为循环主驱动，大致如下：
1、逐个遍历 m数组 ，元素设为 x
2、    用二分法定位 x 在 n数组 中的位置（可能找不到），找到则输出；
3、    因为是升序，所以下一次搜索下限定在 n数组 中不大于 x 位置；
4、循环指导 m数组 遍历完毕。
------解决方案--------------------

引用:

顺序遍历，O(m)。
平方的条件没用上。

哦，最坏是m*n
------解决方案--------------------

        int[] a = {-1,4,5};

        int[] b = {-15,1,3,4,5,7,8,9,10,15};

        int init = 0;

        List<Integer> rtnList = new ArrayList<Integer>();

        for(int i = 0;i<a.length;i++) {

            for(int j = init;j<b.length;j++){

                if (a[i] == b[j]) {

                    init=j+1;

                    rtnList.add(a[i]);

                    break;

                }

            }

        }

------解决方案--------------------
又优化了一下：

int[] a = {-1,4,5};

        int[] b = {-15,1,3,4,5,7,8,9,10,15};

        int init = 0;

        List<Integer> rtnList = new ArrayList<Integer>();

        for(int i = 0;i<a.length;i++) {

            for(int j = init;j<b.length;j++){

                System.out.println("[i:"+i+"][a[i]:"+a[i]+"][j:"+j+"][b[j]:"+b[j]+"]");

                if (a[i] == b[j]) {

                    init=j+1;

                    rtnList.add(a[i]);