Expected number of balls chosen from bag, I throw out everything in the bag with numbers less than the ball's I am mainly confused about my reasoning/solution
Problem: I have a bag of numbers ranging from $1,2... n$. I randomly choose a number and then I throw out all numbers less than that. Then I keep choosing numbers until I've found the largest one. What's the expected number of things I have chosen?
My Argument: I expect on average to have chosen a number of $n/2$ on each pick. Hence, everytime I choose a number, I expect to discard half of them. Hence, the $E(X) = \log_2(n)$
Note that I devised this problem as an equivalent one while trying to solve the "cluster of cars on one long road" question. If this is not equivalent, please let me know but I am confident that it is. As a result of this equivalency, I know my solution is incorrect. However, I cannot pinpoint where the issue arises. 
Probability problem: cars on the road
 A: Here is the result of work in the comments by lulu, Henry, and me.
The expected number of balls is $E[n]=\sum_{i=1}^n\frac 1i=H_n\approx \log n + \gamma + \frac 1{2n}$, the $n^{th}$ harmonic number.  
The recursion is $E[n]=1+\frac 1n\sum_{i=0}^{n-1}E[i]$ because you can imagine putting ball $n$ randomly into an arrangement of $n-1$ balls.  $i$ represents the number of balls before ball $n$.  You will then throw away $E[i]$ balls plus ball $n$.  We define $E[0]=0$ to make this come out properly when ball $n$ is put first in line.  
We have $E[1]=1$ as the base case for strong induction.  Then if $E[j]=H_j$ for all $j$ from $1$ to $k$, 
$$\begin {align}E[k+1]&=1+\frac 1{k+1}\sum_{i=0}^{k}H_i\\
&=1+\frac 1{k+1}\left(1+(1+\frac 12)+(1+\frac 12+\frac 13)+\ldots H_{k}\right)\\
&=1+\frac 1{k+1}\left(k+\frac{k-2}2+\frac{k-3}3+\ldots\frac{k-(k-1)}{k}\right)\\
&=1+H_k-\frac k{k+1}\\&=H_{k+1}\end {align}$$
To go from the second line to the third we count the number of terms $\frac 1m$ and note that it is $n-m$
A: Others in the comments have computed the correct solution.  Here I will only comment on what I think went wrong with the "intuitive" solution of $\log_2 n$.
For slightly easier exposition, I change the game s.t. we throw out all numbers larger than the drawn number.  This way the numbers left are always $\{1, 2, \dots, k\}$ and it is slightly easier (for me) to visualize.
Imagine $n=2^{10}=1024$ and I play the game $G$ as stated.  Meanwhile, you start with an identical bag and play a different game $G'$: at every step, you throw out exactly the larger half of all your remaining numbers.  So your game will take exactly $11$ steps to finish.  Which of us will finish first?
On your first draw, you draw $512$.  On my first draw, I have about $1/2$ chance to do worse than you (i.e. throw out fewer) by drawing $d > 512$ and about $1/2$ chance to do better by drawing $d < 512$.  However, when I do worse, I lost "less than a step" compared to your schedule, whereas when I do better, I can be gaining up to a step ($d \in [256, 511]$) or up to $2$ steps ($d \in [128, 255]$), or up to $3$ steps ($d \in [64, 127]$), etc. compared to your schedule.  Apologies if my boundaries above are not exactly correct, but hopefully you get the idea.  So intuitively, for large $n$ I should win easily.  This also means $E[X] < \log_2 n$.
Another way to look at it: Let $K_j$ be the largest remaining number (also number of remaining numbers) after $j$ steps, with $K_0 = n$.  For game $G'$, we have $\log_2 K_{j+1} - \log_2 K_j = -1$ exactly.  If it were true that for game $G$ we have $E[\log_2 K_{j+1} | K_j] - \log_2 K_j = -1$, then it is plausible that the answer would be $\log_2 n$.  However, in fact $E[\log_2 K_{j+1} | K_j] - \log_2 K_j < -1$.  For this reason $G$ finishes faster than $G'$.
