31
\$\begingroup\$

Given a sorted array of unique positive integers \$A\$ \$(A_0<A_1<\cdots<A_{n-1})\$, and an integer \$t\$, where \$A_0\le t\le A_{n-1}\$. Output the value \$i\$ such that:

  • If \$t \in A\$, \$A_i=t\$.
  • If \$t \notin A\$, \$ \left(i-\left\lfloor i\right\rfloor\right)\cdot A_{\left\lceil i\right\rceil} +\left(\left\lceil i\right\rceil - i\right)\cdot A_{\left\lfloor i\right\rfloor} = t \$. In other words, linearly interpolate between the indices of the two elements of \$A\$ that most narrowly bound \$t\$.

In the above formula, \$\left\lfloor i\right\rfloor\$ means rounding \$i\$ down to integer; \$\left\lceil i\right\rceil\$ means rounding \$i\$ up to integer.

You may also choose 1-indexed array, though you need to adjust the formula and the test cases below accordingly.

Rules

  • This is , shortest code in bytes wins.
  • Floating point errors in output are allowed, but reasonable floating point precision is required. For testcases listed here, your output should be correct with at least 2 decimal places precision.
  • Fraction output is allowed as long as fractions are reduced to their lowest terms.
  • It is fine to use any built-ins in your language. But if built-ins trivialize the question, consider submitting a non-trivial one too.

Testcases

[42], 42 -> 0
[24, 42], 24 -> 0
[24, 42], 42 -> 1
[1, 3, 5, 7, 8, 10, 12], 1 -> 0
[1, 3, 5, 7, 8, 10, 12], 7 -> 3
[1, 3, 5, 7, 8, 10, 12], 12 -> 6
[24, 42], 33 -> 0.5
[24, 42], 30 -> 0.3333333333333333
[1, 3, 5, 7, 8, 10, 12], 2 -> 0.5
[1, 3, 5, 7, 8, 10, 12], 9 -> 4.5
[100, 200, 400, 800], 128 -> 0.28
[100, 200, 400, 800], 228 -> 1.14
[100, 200, 400, 800], 428 -> 2.07
\$\endgroup\$
4
  • 1
    \$\begingroup\$ May we assume the list is non-empty? And what happens if \$ t \$ is outside the range (min ~ max) of the list (e.g. [1, 3, 7], 9)? \$\endgroup\$
    – pxeger
    Commented Nov 12, 2021 at 8:04
  • 2
    \$\begingroup\$ @pxeger \$A_0\le t \le A_{n-1}\$. And the list \$A\$ is always non-empty (otherwise, \$A_0\$ in above formula is not defined). \$\endgroup\$
    – tsh
    Commented Nov 12, 2021 at 8:05
  • 1
    \$\begingroup\$ You'll be the death of me yet, sideways pitchfork operator! \$\endgroup\$
    – Nate T
    Commented Nov 12, 2021 at 12:20
  • 2
    \$\begingroup\$ Wonderfully, Mathematica can do this with builtins: InverseFunction[Interpolation[#,InterpolationOrder->1]][N@#2]&. But it's really long, and also doesn't handle the case where A has only one element. \$\endgroup\$ Commented Nov 13, 2021 at 6:06

20 Answers 20

11
\$\begingroup\$

Python 2, 59 bytes

f=lambda l,t,p=0:l<[t]and 1+f(l[1:],t,l[0])or(t-p)/(l[0]-p)

Try it online!

Outputs one-indexed. Recursively loops through the list element , each time adding 1 to the eventual index output, until reaching an element that's at least t. Then, outputs the fraction of the way t is between the current element and previous element p. This avoids needing to explicitly track which index we're at.

62 bytes

lambda l,t:sum(t>y or(t-x)/(y-x)for x,y in zip([0]+l,l)if x<t)

Try it online!

One-indexed. Same idea as the 64-byte code below. Interprets the input as "intervals" (x, y) of two consecutive elements of the list, starting with left endpoint 0. The output is the sum over each interval of the fraction of it that's less below t, which is 1 for intervals fully below t and 0 for those fully above it.

lambda l,t:sum(min(1,max(0,(t-x)/(y-x)))for x,y in zip([0]+l,l))

Try it online!

The summand is (t-x)/(y-x) clamped between 0 and 1.

\$\endgroup\$
2
  • \$\begingroup\$ max(0,(t-x)/(y-x)) can be max(0,t-x)/(y-x) \$\endgroup\$
    – tsh
    Commented Nov 12, 2021 at 9:54
  • \$\begingroup\$ @tsh I just included the min/max code to illustrate the clamping formula, but let me know if you see a way to cut it down further below 62. \$\endgroup\$
    – xnor
    Commented Nov 12, 2021 at 9:58
7
\$\begingroup\$

Python 3.10, 79 75 67 65 59 bytes

lambda a,t:(t-a[i:=sum(x<t for x in a)])/(a[i]-[0,*a][i])+i

Attempt This Online!

Needs Python 3.10 to use := inside a subscript.

  • t-a[0]and guards against the edge case where a has only one element
  • sum(x<t for x in a) finds the index of the first item x where x<t
  • (t-a[i]/(a[i+1]-a[i])+i just does the linear interpolation

-4 bytes thanks to Kevin Cruijssen

-6 bytes thanks to tsh

-6 bytes thanks to xnor

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Can't 1for x in a if x<t simply be x<t for x in a? \$\endgroup\$ Commented Nov 12, 2021 at 8:31
  • 2
    \$\begingroup\$ len(a)-1 -> t-a[0]; (t-(x:=a[i:=...]))...(a[i+1]-x) -> (t-a[i:=...])...(a[i+1]-a[i]) \$\endgroup\$
    – tsh
    Commented Nov 12, 2021 at 8:43
  • 2
    \$\begingroup\$ lambda a,t:t-a[0]and(t-a[i:=sum(x<t for x in a)])/(a[i]-a[i-1])+i \$\endgroup\$
    – tsh
    Commented Nov 12, 2021 at 8:51
  • 1
    \$\begingroup\$ A different way to handle where i==0: lambda a,t:(t-a[i:=sum(x<t for x in a)])/(a[i]-[0,*a][i])+i \$\endgroup\$
    – xnor
    Commented Nov 12, 2021 at 10:03
6
\$\begingroup\$

JavaScript (ES6), 45 bytes

Expects (t)(A).

t=>g=([c,...a],p=0)=>t>c?1+g(a,c):(t-c)/(c-p)

Try it online!

\$\endgroup\$
6
\$\begingroup\$

MATL, 10 bytes

YYhtfi3$Yn

Inputs are A, then t. The output is 1-based.

Try it online! Or verify all test cases.

Explanation

YY     % Push infinity
h      % Implicit input: row vector A, of length n. Concatenate. This attaches
       % infinity at the end of the vector. This is necessary because
       % interpolation requires a vector of at least 2 entries. The value
       % infinity is used so that it doesn't interfere with the interpolation
tf     % Duplicate, find. This gives the row vector [1 2 3 ... n+1]
i      % Input: integer number t.
3$Yn   % 3-input linear interpolation. Implicit display
\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 44 36 35 34 bytes

Tr@Clip[Ramp[#2-#]/({Set@@#,}-#)]&

Try it online!

Input [A, t]. Returns 0-indexed.

             #2-#                   amount t exceeds each value
                  /({Set@@#,}-#)    / distance to next
                           ,}        (last distance doesn't matter)
   Clip[Ramp[    ]               ]  clamp to [0,1]
Tr@                                 sum
\$\endgroup\$
4
\$\begingroup\$

Python 3 + numpy, 52 bytes

lambda a,t:interp(t,a,argsort(a))
from numpy import*

Try it online!

As ais sorted with no duplicates we can use argsort to save a byte over r_[:len(a)]. Note that the "no duplicates" is important because numpy doesn't use timsort by default but an unstable qsort.

or (same length)

lambda a,t:interp(t,*unique(a,1))
from numpy import*

Try it online!

This uses numpy.unique (which is a nop on a since a has sorted unique values) with the return_index switch set. This returns the indices of the unique values v in the input. As a has sorted unique values this returns 0,1,...,len(a)-1

\$\endgroup\$
4
\$\begingroup\$

Haskell, 42 bytes

q 0
q p(h:r)t|h<t=1+q h r t|d<-h-p=(t-p)/d

Try it online!

Main function is q 0, outputs one-indexed.

43 bytes

l%t|let(h:r)?p|h<t=1+r?h|d<-h-p=(t-p)/d=l?0

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E (legacy), 18 17 13 12 bytes

-D¹¥/ā+s®›Ïθ

First input is the list \$A\$, second input is \$t\$. The output \$i\$ is 1-based.

-1 byte switching to the legacy version of 05AB1E, where [1]/[]=[1] instead of []. In the new version of 05AB1E we therefore had to add a before the θ to account for single-item input-lists. Unfortunately, d was is_int instead of >=0 in the legacy version, so we have to replace it with ®› (>-1) instead, netting at -1 byte.

Try it online or verify all test cases.

Explanation:

-             # Subtract each value in the first (implicit) input-list from the
              # second (implicit) input-integer
 D            # Duplicate this list
  ¹           # Push the first input-list again
   ¥          # Pop and push its deltas / forward differences
    /         # Divide the items at the same positions in the two lists
     ā        # Push a list in the range [1,length] (without popping)
      +       # Add that to each value in the list
       s      # Swap to get the duplicated list again
        ®›    # Check for each whether it's larger than -1 (non-negative)
          Ï   # Only keep the items at the truthy indices
           θ  # Pop and leave the last item
              # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

R, 57 55 bytes

Or R>=4.1, 48 bytes by replacing the word function with \.

-2 bytes thanks to @Dominic van Essen.

function(A,t,r=which(A>=t)[1])r-((A-t)/diff(c(0,A)))[r]

Try it online!

1-indexed.

I couldn't make any built-in linear approximation work, but it doesn't mean that such solution doesn't exist @Dominic van Essen could.

\$\endgroup\$
2
3
\$\begingroup\$

C (clang), 74 71 63 bytes

float r;f(*a,t){for(r=0;*a<t;r++)a++;r-=(*a-t)/(*a-*--a+1e-9);}

Try it online!

  • Saved 3 thanks to @upkajdt suggestion to use a variable instead of printing it.

  • Saved 5 thanks for @ths suggestion to make divisor ~0 by adding 1e-9 to it.

  • Saved another 3 by using float r instead of int n as index counter.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Could be 66 byte if some errors is allowed: float r;n;f(*a,t){for(n=0;*a<t;n++)a++;r=n-(*a-t)/(*a-*--a+1e-9);} \$\endgroup\$
    – tsh
    Commented Nov 13, 2021 at 16:25
  • \$\begingroup\$ @tsh good one! I added these tests [1,999999] with 2, 999998, 1 and 999999 and it seems to work fine \$\endgroup\$
    – AZTECCO
    Commented Nov 14, 2021 at 1:33
3
\$\begingroup\$

Perl 5 + -M5.10.0 -a, 57 bytes

$_>"@F"&&$p<="@F"?say$.-3+("@F"-$p)/($_-$p):0,$p=$_ for<>

Try it online!

Explanation

Naiive approach, but using some Perl var tricks.

-a stores the first input value (the target) in @F which, since we know will only be one value, we can access via "@F". With this we can loop through all other lines of input (for<>) checking if we're greater than the current value and if the $previous was less than of equal to the target and the current ($_) is greater than the target then we output (say) the current index ($. holds the current, 1-indexed, line of input being processed) plus the ratio of the differences between the current and previous, and previous and target.

\$\endgroup\$
3
\$\begingroup\$

Pip -x, 36 32 bytes

Y_>bFNa#y-:$/([bMXy]-N:_<bFNa)|1

Takes the array and the number as command-line arguments. Attempt This Online!

Explanation

Y_>bFNa#y-:$/([bMXy]-N:_<bFNa)|1
      a                           The input array
    FN                            Filter for elements that are not
 _>b                              Greater than the input number
Y                                 Yank that list into y

                          FNa     Filter input array for elements that are not
                       _<b        Less than the input number
                     N:           Minimum such element
              [    ]-             Subtract from each of these:
               b                  Input number
                MXy               Max of y (elements <= b)
                                  We now have a list containing two distances:
                                  from the first element larger than b to b,
                                  and to the last element smaller than b
           $/(               )    Divide the first by the second
                              |1  If the result was 0 or division by 0,
                                  substitute 1 instead
         -:                       Subtract that result from
       #y                         Length of y (elements <= b)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 25 bytes

IΣEθ∧κ⌈⟦⁰⌊⟦¹∕⁻η§θ⊖κ⁻ι§θ⊖κ

Try it online! Link is to verbose version of code. Explanation: Port of @xnor's 64-byte Python solution.

   θ                        Input array
  E                         Map over elements
     κ                      Current index
    ∧                       Logical And
              η             Input value
             ⁻              Minus
               §θ⊖κ         Previous element
            ∕               Divided by
                    ι       Current element
                   ⁻        Minus
                     §θ⊖κ   Previous element
         ⌊⟦¹                Clamp above to 1
      ⌈⟦⁰                   Clamp below to 0
 Σ                          Take the sum
I                           Cast to string
                            Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Perl 5, 75 bytes

sub f{($t,$a,$b)=(@_,9e9);$a<=$t&&$t<=$b?($t-$a)/($b-$a):1+f(@_[0,2..$#_])}

Try it online!

Perl5 versions from 5.32 (TIO has 5.28) got chained comparisons capability which means $a<=$t&&$t<=$b can be shortened to $a<=$t<=$b and save 4 bytes.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I'm not sure you're allowed to limit the input arbitrarily to 9e9 but maybe you can prefix a 0 to the list (which is allowed because the input is guaranteed positive) to the same effect, and call the output 1-indexed, possibly even saving 2 bytes? \$\endgroup\$
    – Neil
    Commented Nov 12, 2021 at 15:46
2
\$\begingroup\$

Ruby, 50 bytes

f=->l,n,z=0{a,*l=l;a<n ?1+f[l,n,a]:1.0*(n-a)/a-=z}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

R, 41 bytes

function(A,t)approx(B,seq(B<-c(A,0)),t)$y

Try it online!

Almost-trivial use of approx built-in: upvote pajonk's non-trivial R answer instead...

\$\endgroup\$
2
\$\begingroup\$

Haskell, 76 73 71 bytes

s!x|(t,y:_)<-span(<x)s,u<-last$0:t=fromIntegral(length$t)-1+(x-u)/(y-u)

Try it online

(I hate explicit conversion (in golfing))

\$\endgroup\$
2
  • \$\begingroup\$ nowhere \$\endgroup\$
    – AZTECCO
    Commented Nov 12, 2021 at 17:54
  • \$\begingroup\$ Thanks! Always forget this trick. \$\endgroup\$
    – daylily
    Commented Nov 13, 2021 at 0:50
1
\$\begingroup\$

APL+WIN, 42 bytes

Prompts for vector followed by integer. 1 indexed.

(m/⍳↑⍴m)+(i-m/v)÷(m←<\(i←⎕)≤v)/v-¯1↓0,v←,⎕

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
1
\$\begingroup\$

PowerShell Core, 84 bytes

$n,$a=$args
for($p=0;$a[++$i]-le$n-and$a[$i]){$p=$i}$p+($n-$a[$p])/($a[$p+1]-$a[$p])

Try it online!

Made of two parts, first find the start index where the array number are greater than the searched number

for($p=0;$a[++$i]-le$n-and$a[$i]){$p=$i}

Then calculate the index:

$p+($n-$a[$p])/($a[$p+1]-$a[$p])
\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 62 bytes

I=A=>t=>(b=A.findIndex(e=>e>=t))-1+(t-A[b-1])/(A[b]-A[b-1])||0

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ does not for console.log(I([42])(42)); \$\endgroup\$
    – tsh
    Commented Apr 12 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.