How to find the longest sub-array within a threshold?
<p>Let's say you have a sorted array of numbers <code>sorted_array</code> and a threshold <code>threshold</code>. What is the fastest way to find the longest sub-array in which all the values are within the threshold? In other words, find indices <code>i</code> and <code>j</code> such that:</p>

<ol>
<li><code>sorted_array[j] - sorted_array[i] &lt;= threshold</code></li>
<li><code>j - i</code> is maximal</li>
</ol>

<p>In case of a tie, return the pair with the smallest <code>i</code>.</p>

<p>I already have a loop-based solution, which I will post as an answer, but I'm curious to see if there's a better way, or a way that can avoid the loop using a vector-capable language or library like NumPy, for example.</p>

<p>Example input and output:</p>

<pre><code>&gt;&gt;&gt; sorted_array = [0, 0.7, 1, 2, 2.5]
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 0.2)
(0, 0)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 0.4)
(1, 2)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 0.8)
(0, 1)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 1)
(0, 2)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 1.9)
(1, 4)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 2)
(0, 3)
&gt;&gt;&gt; longest_subarray_within_threshold(sorted_array, 2.6)
(0, 4)
</code></pre>

<p>Here's a simple loop-based solution in Python:</p>

<pre><code>def longest_subarray_within_threshold(sorted_array, threshold):
    result = (0, 0)
    longest = 0
    i = j = 0
    end = len(sorted_array)
    while i &lt; end:
        if j &lt; end and sorted_array[j] - sorted_array[i] &lt;= threshold:
            current_distance = j - i
            if current_distance &gt; longest:
                longest = current_distance
                result = (i, j)
            j += 1
        else:
            i += 1
    return result
</code></pre>

python arrays algorithm numpy