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
...
endifendif
>>>>>>>>>>
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.