Please help solve this asap! I will upvote!! Thank you!

question 4 (Binary Search Lower Bound) In class we saw how sorting n num- bers using only comparisons, requires (n log n) time, that is no algorithm (no

matter how clever it is) can sort every input array in significantly less time than n log n. Consider now the problem of searching a number x in a sorted array A (that may or may not contain x). We know binary search does this in O(log n) time. Can we do better? In other words, is there a searching algorithm (that uses comparisons) that runs in time o(log n) and correctly determines whether or not an element x appears in A? (hint: think of a tree representation for the execution of any algorithm, as we did in class for sorting. How many leaves are there in the tree? What should the depth of this tree be?)