Binary search in log time on a Turing Machine
Can't be done.

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. 

I am not sure how you intend to represent binary trees (with pointers?). I am sure it is the same case as above. 

That being said, there are models which add random access capabilities to TMs, in particular random-access TMs. You might want to look into those.