Wolfram Language (Mathematica), 34 bytes

Min[⌈.5/#+{-#,#}/2⌉^2+{1,-1}]&

Try it online!

Explanation

The result must be of the form $m^2 pm 1$ for some $m in mathbb{N}$. Solving the inequations $sqrt{m^2+1} - m le k$ and $m - sqrt{m^2-1} le k$, we get $m ge frac{1-k^2}{2k}$ and $m ge frac{1+k^2}{2k}$ respectively. So the result is $operatorname{min}left({leftlceil frac{1-k^2}{2k} rightrceil}^2+1, {leftlceil frac{1+k^2}{2k} rightrceil}^2-1right)$.

Python, 42 bytes

lambda k:((k-1/k)//2)**2+1-2*(k<1/k%2<2-k)

Try it online!

Based on alephalpha's formula, explicitly checking if we're in the $m^2-1$ or $m^2+1$ case via the condition k<1/k%2<2-k.

Python 3.8 can save a byte with an inline assignment.

Python 3.8, 41 bytes

lambda k:((a:=k-1/k)//2)**2-1+2*(a/2%1<k)

Try it online!

These beat my recursive solution:

50 bytes

f=lambda k,x=1:k>.5-abs(x**.5%1-.5)>0 or-~f(k,x+1)

Try it online!

05AB1E, 16 bytes

nD(‚>I·/înTS·<-ß

Port of @alephalpha's Mathematica answer, with inspiration from @Sok's Pyth answer, so make sure to upvote both of them!

Try it online or verify all test cases.

Explanation:

n                 # Take the square of the (implicit) input

                  #  i.e. 0.05 → 0.0025

 D(‚              # Pair it with its negative

                  #  i.e. 0.0025 → [0.0025,-0.0025]

    >             # Increment both by 1

                  #  i.e. [0.0025,-0.0025] → [1.0025,0.9975]

     I·           # Push the input doubled

                  #  i.e. 0.05 → 0.1

       /          # Divide both numbers with this doubled input

                  #  i.e. [1.0025,0.9975] / 0.1 → [10.025,9.975]

        î         # Round both up

                  #  i.e. [10.025,9.975] → [11.0,10.0]

         n        # Take the square of those

                  #  i.e. [11.0,10.0] → [121.0,100.0]

          TS      # Push [1,0]

            ·     # Double both to [2,0]

             <    # Decrease both by 1 to [1,-1]

              -   # Decrease the earlier numbers by this

                  #  i.e. [121.0,100.0] - [1,-1] → [120.0,101.0]

               ß  # Pop and push the minimum of the two

                  #  i.e. [120.0,101.0] → 101.0

                  # (which is output implicitly)

JavaScript (ES7),  51  50 bytes

f=(k,n)=>!(d=(s=n**.5)+~(s-.5))|d*d>k*k?f(k,-~n):n

Try it online!

(fails for the test cases that require too much recursion)

Non-recursive version,  57  56 bytes

k=>{for(n=1;!(d=(s=++n**.5)+~(s-.5))|d*d>k*k;);return n}

Try it online!

Or for 55 bytes:

k=>eval(`for(n=1;!(d=(s=++n**.5)+~(s-.5))|d*d>k*k;);n`)

Try it online!

(but this one is significantly slower)

J, 39 29 bytes

[:<./_1 1++:*:@>.@%~1+(,-)@*:

NB. This shorter version simply uses @alephalpha's formula.

Try it online!

39 bytes, original, brute force

2(>:@])^:((<+.0=])(<.-.)@(-<.)@%:)^:_~]

Try it online!

Handles all test cases

Japt, 18 16 bytes

-2 bytes from Shaggy

_=¬u1)©U>½-½aZ}a

Try it online!

Perl 6, 33 bytes

-1 byte thanks to Grimy

{first $_>*.sqrt*(1|-1)%1>0,1..*}

Try it online!

Pyth, 22 21 bytes

hSm-^.Ech*d^Q2yQ2d_B1

Try it online here, or verify all the test cases at once here.

Another port of alephalpha's excellent answer, make sure to give them an upvote!

hSm-^.Ech*d^Q2yQ2d_B1   Implicit: Q=eval(input())

                  _B1   [1,-1]

  m                     Map each element of the above, as d, using:

           ^Q2            Q^2

         *d               Multiply by d

        h                 Increment

       c      yQ          Divide by (2 * Q)

     .E                   Round up

    ^           2         Square

   -             d        Subtract d

 S                      Sort

h                       Take first element, implicit print

Edit: Saved a byte, thanks to Kevin Cruijssen

APL (Dyalog Unicode), 27 bytes^SBCS

⌊/0~⍨¯1 1+2*⍨∘⌈+⍨÷⍨1(+,-)×⍨

Try it online!

Monadic train taking one argument. This is a port of alephalpha's answer.

How:

⌊/0~⍨¯1 1+2*⍨∘⌈+⍨÷⍨1(+,-)×⍨ ⍝ Monadic train



                         ×⍨ ⍝ Square of the argument

                   1(+,-)   ⍝ 1 ± that (returns 1+k^2, 1-k^2)

                 ÷⍨         ⍝ divided by

               +⍨           ⍝ twice the argument

             ∘⌈             ⍝ Ceiling

          2*⍨               ⍝ Squared

     ¯1 1+                  ⍝ -1 to the first, +1 to the second

  0~⍨                       ⍝ Removing the zeroes

⌊/                          ⍝ Return the smallest

C# (Visual C# Interactive Compiler), 89 85 bytes

k=>{double n=1,p;for(;Math.Abs(Math.Round(p=Math.Sqrt(n))-p)>k|p%1==0;n++);return n;}

Try it online!

-4 bytes thanks to Kevin Cruijssen!

Java (JDK), 73 bytes

k->{for(double i=1,j;;){j=Math.sqrt(++i)%1;if(j>0&&j<k||1-j<k)return i;}}

Try it online!

Java 8, 85 bytes

n->{double i=1,p;for(;Math.abs(Math.round(p=Math.sqrt(i))-p)>n|p%1==0;i++);return i;}

Port of EmbodimentOfIgnorance's C# .NET answer.

Try it online.

The Math.round can alternatively be this, but unfortunately it's the same byte-count:

n->{double i=1,p;for(;Math.abs((int)((p=Math.sqrt(i))+.5)-p)>n|p%1==0;i++);return i;}

Try it online.

MathGolf, 16 bytes

²_b*α)½╠ü²1bαm,╓

Try it online!

Not a huge fan of this solution. It is a port of the 05AB1E solution, which is based on the same formula most answers are using.

Explanation

²                  pop a : push(a*a)

 _                 duplicate TOS

  b                push -1

   *               pop a, b : push(a*b)

    α              wrap last two elements in array

     )             increment

      ½            halve

       ╠           pop a, b, push b/a

        ü          ceiling with implicit map

         ²         pop a : push(a*a)

          1        push 1

           b       push -1

            α      wrap last two elements in array

             m     explicit map

              ,    pop a, b, push b-a

               ╓   min of list

Forth (gforth), 76 bytes

: f 1 begin 1+ dup s>f fsqrt fdup fround f- fabs fdup f0> fover f< * until ;

Try it online!

Explanation

Starts a counter at 1 and Increments it in a loop. Each iteration it checks if the absolute value of the counter's square root - the closest integer is less than k

Code Explanation

: f                    start a new word definition

  1                    place a counter on the stack, start it at 1

  begin                start and indefinite loop

    1+                 add 1 to the counter

    dup s>f            convert a copy of the counter to a float

    fsqrt              get the square root of the counter

    fdup fround f-     get the difference between the square root and the next closes integer

    fabs fdup          get the absolute value of the result and duplicate

    f0>                check if the result is greater than 0 (not perfect square)

    fover f<           bring k to the top of the float stack and check if the sqrt is less than k

    *                  multiply the two results (shorter "and" in this case)

  until                end loop if result ("and" of both conditions) is true

;                      end word definition

Jelly, 13 bytes

I have not managed to get anything terser than the same approach as alephalpha

- go upvote his Mathematica answer!

²;N$‘÷ḤĊ²_Ø+Ṃ

Try it online!

How?

²;N$‘÷ḤĊ²_Ø+Ṃ - Link: number, n (in (0,1))

²             - square n        -> n²

   $          - last two links as a monad:

  N           -   negate        -> -(n²)

 ;            -   concatenate   -> [n², -(n²)]

    ‘         - increment       -> [1+n², 1-(n²)]

      Ḥ       - double n        -> 2n

     ÷        - divide          -> [(1+n²)/n/2, (1-(n²))/n/2]

       Ċ      - ceiling         -> [⌈(1+n²)/n/2⌉, ⌈(1-(n²))/n/2⌉]

        ²     - square          -> [⌈(1+n²)/n/2⌉², ⌈(1-(n²))/n/2⌉²]

          Ø+  - literal         -> [1,-1]

         _    - subtract        -> [⌈(1+n²)/n/2⌉²-1, ⌈(1-(n²))/n/2⌉²+1]

            Ṃ - minimum         -> min(⌈(1+n²)/n/2⌉²-1, ⌈(1-(n²))/n/2⌉²+1)