Consider randomized 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 to 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.

Use linearity of expectations.

Please don't copy/paste an answer, the one that gets copy/pasted around has incorrect work.