Floating Point indexOf

Question

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 code-golf, 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

• pxeger: 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)?
• tsh: @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).
• Nate T: You'll be the death of me yet, sideways pitchfork operator!
• Greg Martin: 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.

Answer 1

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.

• tsh: max(0,(t-x)/(y-x)) can be max(0,t-x)/(y-x)
• xnor: @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.

Answer 2

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

• Kevin Cruijssen: Can't 1for x in a if x<t simply be x<t for x in a?
• tsh: len(a)-1 -> t-a[0]; (t-(x:=a[i:=...]))...(a[i+1]-x) -> (t-a[i:=...])...(a[i+1]-a[i])
• tsh: lambda a,t:t-a[0]and(t-a[i:=sum(x<t for x in a)])/(a[i]-a[i-1])+i
• xnor: 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

Answer 3

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!

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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!

Answer 8

05AB1E (legacy), (削除) 18 (削除ここまで) (削除) 17 (削除ここまで) (削除) 13 (削除ここまで) 12 bytes

-D1\/ā+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 1š 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
 1 # 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)

Answer 9

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.

• Dominic van Essen: 55 bytes with 1-indexed output...
• Dominic van Essen: "but it doesn't mean that such solution doesn't exist"...

Answer 10

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.

• tsh: 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);}
• AZTECCO: @tsh good one! I added these tests [1,999999] with 2, 999998, 1 and 999999 and it seems to work fine

Answer 11

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.

Answer 12

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)

Answer 13

Charcoal, 25 bytes

IΣEθ∧κ⌈⟦0⌊⟦1∕−η§θ⊖κ−ι§θ⊖κ

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
 ⌊⟦1 Clamp above to 1
 ⌈⟦0 Clamp below to 0
 Σ Take the sum
I Cast to string
 Implicitly print

Answer 14

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.

• Neil: 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?

Answer 15

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!

Answer 16

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...

Answer 17

Haskell, ^{(削除) 76 (削除ここまで) (削除) 73 (削除ここまで)} 71 bytes

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

Try it online

(I hate explicit conversion (in golfing))

• AZTECCO: nowhere
• daylily: Thanks! Always forget this trick.

Answer 18

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

Answer 19

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])

Answer 20

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!

• tsh: does not for console.log(I([42])(42));