Theorem 1. For any $\epsilon>0$, there is a $(1+\epsilon)$-approximation algorithm that makes $O(\epsilon^{-1}\log n)$ queries.
Note that if $\epsilon$ is arbitrarily small but constant,
the algorithm makes $O(\log n)$ queries.
Before we prove the theorem, we prove the following utility lemma:
Lemma 1. Let $P_1, P_2, \ldots, P_m$ be a partition of the indices $[n]$, and for each $\ell\in [m]$ let $a(\ell)$ be a $(1+\epsilon)$-approximate solution to the subproblem induced by $P_\ell$. That is,
$$x_{a(\ell)} + y_{a(\ell)} \le (1+\epsilon) \big(\min_{i\in P_\ell} x_i + y_i\big).$$
Let $a(\ell^*)$ be the best of these approximation solutions. That is,
$\ell^* = \arg\min_\ell \{x_{a(\ell)} + y_{a(\ell)}\}$. Then $a(\ell^*)$ is a $(1+\epsilon)$-approximate solution to the original problem.
Proof. For any $i\in[n]$, we have, for $\ell$ such that $i\in P_\ell$,
$$x_i + y_i
\ge (x_{a(\ell)} + y_{a(\ell)})/(1+\epsilon)
\ge (x_{a(\ell^*)} + y_{a(\ell^*)})/(1+\epsilon).~~~~~\Box$$
Now we prove the theorem. Here is the algorithm. First, using a single binary search on $x_i/y_i$, find $h = \max\{i\in [n] : x_i / y_i \le 1\}$. (Note that $x_i/y_i$ is increasing with $i$, so this takes $O(\log n)$ queries.)
Now partition the index set $[n]$ into two parts: $\{1, \ldots, h\}$ and $\{h+1, \ldots, n\}$. First compute a $(1+\epsilon)$-approximate solution to the subproblem induced by the first part $\{1, \ldots, h\}$ as follows.
Fix integer $k = \lceil 1/\epsilon\rceil$.
Using $k-1$ binary searches, partition the index set $[h]$ into $k$ parts, where, for each $\ell\in [k]$, each index $i$ in the $\ell$th part $P_\ell$ satisfies
$$(\ell-1)/k \le x_i / y_i \le \ell/k.$$
[For intuition, note that this condition is equivalent to
$$y_i (1+(\ell-1)/k) \le x_i + y_i \le y_i(1 + \ell/k),$$
so that within the part we have
$$x_i + y_i = (1+O(1/k))(1+(\ell-1)/k) y_i,$$
that is, the value $(1+(\ell-1)/k) y_i$ is a $(1+O(\epsilon))$-approximation to $x_i + y_i$.]
Now, for each $\ell\in [k]$, let $a(\ell)$ be the index $i$ in the $\ell$th part $P_\ell$ minimizing $y_i$. Note that $y_i$ is non-increasing with $i$, so we can just take $a(\ell) \gets \min P_\ell$, without doing additional queries.
Note that $a(\ell)$ is a $(1+\epsilon)$-approximate solution to the subproblem induced by $P_\ell$, because for any $i\in P_\ell$ we have
$$x_i + y_i
\ge y_i(1+(\ell-1)/k)
\ge y_{a(\ell)}(1+(\ell-1)/k)
\ge (x_{a(\ell)} + y_{a(\ell)})\alpha(k, \ell),$$
where
$$\alpha(k, \ell) = \frac{1+(\ell-1)/k)}{1+\ell/k}
= \frac{k+\ell-1}{k+\ell}
= 1 - \frac{1}{k+\ell}
\ge 1- \frac{1}{k+1}
= \frac{1}{1+1/k}
\ge \frac{1}{1+\epsilon}.$$
By Lemma 1, this gives us a $(1+\epsilon)$-approximate solution to the first part $[h]$ of $[n]$, using $O(\epsilon^{-1} \log n)$ queries. Similarly (exchanging the roles of $x$ and $y$) we can compute a $(1+\epsilon)$-approximate solution to the second part $[n]\setminus[h]$ using $O(\epsilon^{-1} \log n)$ queries. By Lemma 1, taking the best of these two solutions gives us a $(1+\epsilon)$-approximate solution to the original problem, in $O(\epsilon^{-1} \log n)$ queries.$~~~\Box$
