I have searched around and it seems like it is impossible for a Turing machine to implement binary search for an arbitrary sized array. How can a turing machine be called universally computable if it can't perform a simple operation other models of computation can do with ease?
Turing Machines can simulate binary search, in the sense that they can compute whatever you can compute using binary search. You seem to be confusing computability and complexity, which are two different things.
Roughly speaking, computability is about what we are able to compute in a given model of computation. We believe Turing machines to be an universal model of computation. All powerful-enough (i.e., Turing complete) models are equivalent to a Turing Machine.
Complexity is about how long it takes to compute something (actually, this is not restricted to time). Different models of computation are not necessarily equivalent complexity-wise.