<div dir="ltr">I guess I'm probably late to the party -- but since your dataset is relatively modest in size, you can afford to be a little more slow for the benefit of shorter code. The following function will basically do it:<div>

<br></div><div><div>import numpy as np</div><div><br></div><div>def closest_index(a, b):</div><div>    idx2 = np.minimum(len(a) - 1, np.searchsorted(a, b))</div><div>    idx1 = np.maximum(0, idx2 - 1)</div><div>    np.putmask(idx1, np.abs(a[idx1] - b) > np.abs(a[idx2] - b), idx2)           </div>

<div>    return idx1</div></div><div><br></div><div style>For some explanation.. when you call np.searchsorted(a, b[i]), it will return an index x where following holds: a[x-1] < b[i] <= a[x]. So after you get that x, there are only two candidates for b[i]: x-1 or x.</div>

<div><br></div><div style>The rest is just vectorizing that using numpy's array manipulation functions, and some bound checking. The time complexity for this would be O(m*lgn) which is slightly inferior to O(n+m+mlgm) but numpy functions are in C and they are blazing fast.</div>

<div style><br></div><div style>Here's a little more verbose version complete with tests: <a href="https://gist.github.com/4481357">https://gist.github.com/4481357</a></div><div style><br></div></div><div class="gmail_extra">

<br><br><div class="gmail_quote">2013/1/5 Oren Livne <span dir="ltr"><<a href="mailto:livne@uchicago.edu" target="_blank">livne@uchicago.edu</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

Thanks so much to all of you! I can sort B and sweep through both arrays once, as suggest.<span class="HOEnZb"><font color="#888888"><br>
Oren</font></span><div class="im HOEnZb"><br>
<br>
On 1/4/2013 5:20 PM, Rajesh Sankaran wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
What about sorting B ( cost - O(nlog(n)))?  Once sorted, as you advance in B array, your A pointer will only move forward.<br>
You will go through each of the two arrays only once (cost O(m+n)).<br>
<br>
-- <br>
Raj<br>
<br>
On Fri, 04 Jan 2013 16:11:25 -0600, Oren Livne <<a href="mailto:livne@uchicago.edu" target="_blank">livne@uchicago.edu</a>> wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Dear All,<br>
<br>
I have an sorted array A of size 3.4M of positive integers and an array B of size 300,000 of positive integers. I would like to output for each x in B the value in A that is closest to it. This is easy to do for a single element, but I need an efficient implementation for the entire of B. Any suggestions?<br>


<br>
Thanks,<br>
Oren<br>
</blockquote></blockquote>
<br>
<br></div><div class="im HOEnZb">
-- <br>
A person is just about as big as the things that make him angry.<br>
<br></div><div class="HOEnZb"><div class="h5">
______________________________<u></u>_________________<br>
Chicago mailing list<br>
<a href="mailto:Chicago@python.org" target="_blank">Chicago@python.org</a><br>
<a href="http://mail.python.org/mailman/listinfo/chicago" target="_blank">http://mail.python.org/<u></u>mailman/listinfo/chicago</a><br>
</div></div></blockquote></div><br></div>