[Chicago] Closest Index

Rajesh Sankaran rajeshxsankaran at gmail.com
Sat Jan 5 00:20:21 CET 2013


What about sorting B ( cost - O(nlog(n)))?  Once sorted, as you advance in  
B array, your A pointer will only move forward.
You will go through each of the two arrays only once (cost O(m+n)).

--
Raj

On Fri, 04 Jan 2013 16:11:25 -0600, Oren Livne <livne at uchicago.edu> wrote:

> Dear All,
>
> 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?
>
> Thanks,
> Oren


More information about the Chicago mailing list