To solve the above question, the professor told me to use the property that the expected height of a randomly built binary search tree on n distinct keys is O(log n). I know the proof of that, however, I don't know how to visualize the binary search algorithm in the given question into subproblems forming a binary search tree. Can you help me how to get there. If you have an alternative solution for this that would help too.

Consider the following silly randomized variant of binary search. You are given a sorted array A of n integers and the integer v that you are searching for is chosen uniformly at random from A. Then instead of comparing v with the value in the middle of the array, the randomized binary search variant chooses a random number r from 1 to n and it compares v with A[r. Depending on whether v is larger or smaller, this process is repeated recursively on the left sub-array or the right sub-array, until the location of v is found. Prove a tight bound on the expected running time of this algorithm