added 2 characters in body

Source Link

edited Jul 3, 2018 at 7:14

JavaScript (Node.js), 8180 bytes

f=x=>g=(x,y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?fg(x,y,i+!t,j+t)+!t*(d>0?d:-d):0

It run in O(|X|+|Y|): Every recursion run in O(1), and it recursive |X|+|Y| times.
- x, y are passed by reference, which do not copy the content
1/v is falsy if x[i] is out of range, truthy otherwise
t -> d>y[j+1]-v -> v+v>y[j]+y[j+1] is false as long as following conditions meet. And which means y[j] is the number closest to v in y
- v is less than (y[j]+y[j+1])/2, or
- y[j+1] is out of range, which would convert to NaN, and compare to NaN yield false
  - that's why we cannot flip the > sign to save 1 more byte
t is always a boolean value, and * convert it to 0/1 before calculating

JavaScript (Node.js), 81 bytes

f=(x,y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?f(x,y,i+!t,j+t)+!t*(d>0?d:-d):0

It run in O(|X|+|Y|): Every recursion run in O(1), and it recursive |X|+|Y| times.
- x, y are passed by reference, which do not copy the content
1/v is falsy if x[i] is out of range, truthy otherwise
t -> d>y[j+1]-v -> v+v>y[j]+y[j+1] is false as long as following conditions meet. And which means y[j] is the number closest to v in y
- v is less than (y[j]+y[j+1])/2, or
- y[j+1] is out of range, which would convert to NaN, and compare to NaN yield false
  - that's why we cannot flip the > sign to save 1 more byte
t is always a boolean value, and * convert it to 0/1 before calculating

x=>g=(y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?g(y,i+!t,j+t)+!t*(d>0?d:-d):0

It run in O(|X|+|Y|): Every recursion run in O(1), and it recursive |X|+|Y| times.
- x, y are passed by reference, which do not copy the content
1/v is falsy if x[i] is out of range, truthy otherwise
t -> d>y[j+1]-v -> v+v>y[j]+y[j+1] is false as long as following conditions meet. And which means y[j] is the number closest to v in y
- v is less than (y[j]+y[j+1])/2, or
- y[j+1] is out of range, which would convert to NaN, and compare to NaN yield false
  - that's why we cannot flip the > sign to save 1 more byte
t is always a boolean value, and * convert it to 0/1 before calculating

added 564 characters in body

Source Link

edited Jul 2, 2018 at 8:16

f=(x,y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?f(x,y,i+!t,j+t)+!t*(d>0?d:-d):0

It run in O(|X|+|Y|): Every recursion run in O(1), and it recursive |X|+|Y| times.
- x, y are passed by reference, which do not copy the content

t -> d>y[j+1]-v -> v+v>y[j]+y[j+1] is false as long as following conditions meet. And which means y[j] is the number closest to v in y
- v is less than (y[j]+y[j+1])/2, or
- y[j+1] is out of range, which would convert to NaN, and compare to NaN yield false
  - that's why we cannot flip the > sign to save 1 more byte

f=(x,y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?f(x,y,i+!t,j+t)+!t*(d>0?d:-d):0

f=(x,y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?f(x,y,i+!t,j+t)+!t*(d>0?d:-d):0

It run in O(|X|+|Y|): Every recursion run in O(1), and it recursive |X|+|Y| times.
- x, y are passed by reference, which do not copy the content

t -> d>y[j+1]-v -> v+v>y[j]+y[j+1] is false as long as following conditions meet. And which means y[j] is the number closest to v in y
- v is less than (y[j]+y[j+1])/2, or
- y[j+1] is out of range, which would convert to NaN, and compare to NaN yield false
  - that's why we cannot flip the > sign to save 1 more byte

Source Link

created Jul 2, 2018 at 6:53

f=(x,y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?f(x,y,i+!t,j+t)+!t*(d>0?d:-d):0