Efficiently looping through lists in Python
<p>I need to make a python function which, given ordered list <code>a</code> and <code>b</code> returns <code>True</code> if there exists an item in a for which holds that there is an item in <code>b</code> that is <code>a+1</code>.</p>

<p>This is of course easily done by using something like this:</p>

<pre><code>for item in a:
  if (a+1 in b):
     return True
</code></pre>

<p>However, I need to make this as efficient as possible because the function will be used to process loads of data. The tip that was given me was to use the <code>iter()</code> and <code>next()</code> operations, but I have not found a way to use these for effecient processing yet. Does anyone know how to implement these, or use another fast algorythm?
Thanks in advance.</p>

<p>I can see two options that are more efficient.</p>

<ol>
<li>Go through each element in <code>a</code>, and perform a binary search for <code>element+1</code> in <code>b</code>.</li>
</ol>

<p>Time complexity: O(n*log(m)) where n = <code>|a|</code> and m = <code>|b|</code>.</p>

<pre><code>    for element in a:
        if binary_search(a, element+1):
            return True
    return False
</code></pre>

<ol start="2">
<li>Increment two counters through [0,<code>|a|</code>) and [0,<code>|b|</code>), say <code>i</code> and <code>j</code>.  Loop while <code>i</code> is less than <code>|a|</code> and <code>j</code> is less than <code>|b|</code>.  Compare <code>a[i] + 1</code> with <code>b[j]</code>.  If they are equal, return <code>True</code>.  If the value of <code>a[i] + 1 &gt; b[j]</code>, increment <code>j</code>.  Otherwise, increment <code>i</code>.</li>
</ol>

<p>Time complexity: O(n+m) where n = <code>|a|</code> and m = <code>|b|</code>.</p>

<pre><code>    i = 0
    j = 0
    while i &lt; len(a) and j &lt; len(b):
        if a[i] + 1 == b[j]:
            return True
        elif a[i] + 1 &gt; b[j]:
            j += 1
        else:
            i += 1
    return False            
</code></pre>

python list loops iterator