# Binary search in log time on a Turing Machine

I was thinking about TM (Turing Machine) as a computation model, and I came up with the following question :

Is it possible to make a TM that answers binary search (tell wether $$x$$ belong to a sorted array $$A$$) in $$\log$$ time ? That is, is it possible to simulate random access on a TM ?

My thoughts so far are that it is not possible, because the memory of a TM has to be accessed sequentially, e.g. in binary search, reading the element at $$n/2$$ in the array (first comparison for binary search) takes at least $$n/2$$ steps.

If it is indeed impossible, does the same hold for structures like binary trees ?

Assuming the TM receives its input as $$\langle x, A \rangle$$ (i.e., $$x$$ followed by $$A$$) and that $$x$$ as well as the array contents are binary encoded, then the asymptotic log-time bound ensures almost all inputs are such that the TM is not even able to read past $$x$$, let alone search the array. Even if you bound the contents of the array (i.e., a constant number of values, one value per cell), the TM can only read up to the first $$\log n$$ entries for a list of size $$n$$; searching for an $$x$$ strictly larger than those entries will fail.