title: How reduce the complexity of the searching in two lists algorithm?
body: <p>I have to find some common items in two lists. I <strong>cannot sort</strong> it, order is important. Have to find how many elements from <code>secondList</code> occur in <code>firstList</code>. Now it looks like below:</p>
  
  <pre><code>int[] firstList;
  int[] secondList;
  int iterator=0;
  for(int i:firstList){
   while(i &lt;= secondList[iterator]/* two conditions more */){
         iterator++;
         //some actions
     }
  }
  </code></pre>
  
  <p>Complexity of this algorithm is <strong>n x n</strong>. I try to reduce the complexity of this operation, but I don't know how compare elements in different way? Any advice?</p>
  
  <p><strong>EDIT:</strong>
  Example: <code>A=5,4,3,2,3</code> <code>B=1,2,3</code>
  We look for pairs <code>B[i],A[j]</code>
  Condition: 
  when </p>
  
  <pre><code>B[i] &lt; A[j]
           j++ 
  </code></pre>
  
  <p>when </p>
  
  <pre><code>B[i] &gt;= A[j]
           return B[i],A[j-1]
  </code></pre>
  
  <p>next iteration through the list of <strong>A</strong> to an element <strong>j-1</strong> (mean <code>for(int z=0;z&lt;j-1;z++)</code>)
  <em>I'm not sure, Did I make myself clear?</em>
  <strong>Duplicated are allowed.</strong></p>