Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time
This is an interesting question.

Here is an algorithm.


Iterate through the array to obtain $m$ and $M$. If $m=M$, we are done. Otherwise, let $\delta=\frac{M-m}n$. 
For $i=0,1,\cdots,n+1$, let $L_i$ be an empty list of numbers. 
Iterate through the array again. For each $a_j$, if $\lfloor (a_j-m)/\delta\rfloor=k$, then append $a_j$ to $L_k$ and $L_{k+1}$.
Iterate through $L_0, L_1, \cdots, L_{n+1}$. Skip $L_k$ if there is at most one number in it. Otherwise process $L_k$ as follows.


If there are two numbers, compute their difference. If it is not more than $\delta$, we are done.
If there are three numbers or more, select arbitrarily three of them. Compute all three differences between each pair of them. There must be one pair of numbers whose difference is smaller than $\delta$. Select that pair and we are done.



It is not difficult to see the above algorithm is correct and its time-complexity is $\Theta(n)$.



The above algorithm could be sped up if $L_k$ or $L_{k+1}$ is processed just as in step 4 while we are still running step 3. It would be an interesting but hard problem to determine when will be the optimal time to start processing, assuming for example, $a_j$'s are uniformly and independently distributed in $[m,M]$. Starting from $a_{n//2}$ (or $a_{\lfloor n/\log n\rfloor}$ or even $a_{\lfloor n/\sqrt n\rfloor}$?) should improve the speed in general, I believe. However, the worst time-complexity cannot be better than $\Omega(n)$. 

Instead of step 3, we could also put $a_j$ to $L_{k}$, $L_{k+1}$ and $L_{k+2}$ if $\lfloor 2(a_j-m)/\delta\rfloor=k$ and adapt step 2 and 4 accordingly.



It might be interesting how I found this algorithm. I literally recited Polya's principle, "do you know a related problem?". I recalled that finding duplicate elements in an array using hash table takes linear time of $n$. Could I apply that conclusion? Or the way of using hash table? What is a hash table and how can I create a hash here? If I can put nearby numbers in the same slot, I can considered them as the same, then the algorithm might work. The it dawned on me that I could use the location of $a_j$ as "its hash". However, two numbers that are very close could be mapped to different hashes, which breaks the promise. If one hash is not enough, how about two hashes? I could almost see the light on the other side of the tunnel. After a few minor adjustments, I arrived at the current answer. (Somehow I missed Yuval's nice method by divide and conquer, which, in hindsight, should not have been difficult to find.)



Motivated by Yuval's emphasis on randomization and practice, I would like to ask the following question.

Let $n+1$ numbers be (uniformly and) independently distributed in $[0,1]$. Is there an algorithm that finds two elements whose absolute difference is not greater than $1/n$ with sublinear average time-complexity? (I believe the naive algorithm that inserts $a_j$ into a (balanced) binary search tree works. Who has a proof?)