Nadya:

>>>>>>>>>>
Idea:

test = arr[int(k/2)]
if X < test && We don't need to check the rest of the array
   test = arr[int(k/4))
   if X < test && we don't need to check 3/4 of the array
      ...
   endif
endif

>>>>>>>>>>

Good try but no cigar.

This algorithm works if you scan the array and for each value Y, you apply your idea to X-Y. However, the algorithm is of order n * Log(n) (worse than linear, better than quadratic) and not linear.

Daniel