Potential method for dynamic binary search
What about this potential function

$$\Phi = \sum_{i=0}^{k-1} n_i \cdot 2^i \cdot \left((k-1) - i \right),$$

where $k = \lceil \lg(n+1) \rceil$ (please check the details related to the stuff of $\lg$ and $\lceil \rceil$).

That is, each element in "depth" $n_i (i = 0, \cdots, k-1)$ has its "individual potential" $(k-1) - i$. The intuition is the higher the element is, the more potential it has and the higher price you pay to move it down (until the bottom). The whole potential of the data structure at any state is the sum of the potential of its all elements. 

With this potential function, the amortized cost for the insertion of an element which does not cause any merge (i.e., the element is inserted into the empty subarray $A_0$) is

$$\hat{c} = 1 \quad (\text{actual cost for creation}) + (k-1) \quad (\text{increment of the potential function}) \\ = k = \lceil \lg(n+1) \rceil.$$

On the other hand, the amortized cost for the insertion of an element which causes $t$ merges is (please check the computation):

$$\hat{c} = 1 + \sum_{i=1}^{t} 2^t - (\sum_{i=0}^{i=t-1} 2^i (t-i)) \quad (\text{the potential decreases}) \\ = (2^{t+1} - 1) - (t(2^t-1) - (2^t t-2^{t+1} +2)) \\ = t + 1 \le k = \lceil \lg(n+1) \rceil.$$

Therefore, the amortized cost for each insertion is $O(\lg n)$.



Explanation for the decrement of the potential function $\sum_{i=0}^{i=t-1} 2^i (t-i)$:
First, each subarray $A_i,i=0,⋯,t−1$ contains $2^i$ elements. Secondly, each element in $A_i$ will be moved down to the $t$-th level subarray $A_t$, decreasing its potential by $t−i$, i.e., from $(k−1)−i$ to $(k−1)−t$. Summing them up, we obtain the total decrement of the potential function.