Optimizing a strictly monotone function
Given the discrete intervals $[a,b]\subset\mathbb{N}$ and $[c,d]\subset\mathbb{N}$, we might be able to do slightly better than binary search using the midpoint without utilizing gradient descent.

Instead, we could use binary search with $x=a+\lfloor\frac{y-c}{d-c}(b-a)\rfloor$, which corresponds to the below intersection of the dotted purple line denoting $y$ and the line from $f(a)=c$ to $f(b)=d$.



The red and blue lines represent the extremes of strictly monotonic functions.
When $f$ is linear, this would immediately find the closest $x$ (which is a big improvement over binary search with the midpoint). Without additional information, I think linearity is the best assumption you can make; there are as many concave functions as convex functions, as well as functions that switch. 

One justification for not using gradient descent is if an array $[a,a+1,\dots,b]$ is simply mapped to another array of the same size but different range of data $[c,d]$, which is  randomly chosen (and sorted).

Otherwise, you could use Newton's method as suggested by Dave Clarke or gradient descent as suggested by Raphael, which I just learned are different.