The proof is from the book Advanced Calculus: An Introduction to Linear Analysis by Leonard F. Richardson
Theorem (Bolzano-Weierstrass): Let $x_n$ be any bounded sequence of real numbers, so that there exists $M \in \mathbb{R}$ such that $|x_n|\leq M$ for all $n$. Then there exists a convergent subsequence $x_{n_k}$ of $x_n$. That is, there exists a subsequence $x_{n_k}$ that converges to some $L \in [-M,M]$.
Proof: We will use the method of interval-halving introduced previously to prove the existence of least upper bounds. Let $a_1=-M$ and $b_1=M$. So $x_n \in [a_1,b_1]$, for all $n \in \mathbb{N}$. Let $x_{n_1}=x_1$. Now divide $[a_1,b_1]$ in half using $\frac{a_1+b_1}{2}=0$.
i. If there exist $\infty$-many values of $n$ such that $x_n \in [a_1,0]$, then let $a_2=a_1$ and $b_2=0$.
ii. But if there do not exist $\infty$-many such terms in $[a_1,0]$,
then there exist $\infty$-many such terms in $[0,b_1]$. In that case,
let $a_2=0$ and $b_2=b_1$.
Now, since there exist $\infty$-many terms of $x_n$ in $[a_2,b_2]$, pick any $n_2>n_1$ such that $x_{n_2} \in [a_2,b_2]$ in half and pick one of the halves $[a_3,b_3]$ having $\infty$-many terms of $x_n$ in it. Then pick $n_3>n_2$ such that $x_{n_3} \in [a_3,b_3]$. Observe that
$$|b_k-a_k|=\frac{2M}{2^{k-1}} \rightarrow 0$$
as $k \rightarrow \infty$. So if $\epsilon > 0$, there exists $K$ such that $k \geq K$ implies $|b_k-a_k|< \epsilon$. Thus if $j$ and $k \geq K$, we have $|x_{n_j}-x_{n_k}|<\epsilon$ as well. Hence, $x_{n_k}$ is a Cauchy sequence and must converge. Since $[-M,M]$ is a closed interval, we know from a previous exercise that $x_{n_k} \rightarrow L$ as $k\rightarrow \infty$ for some $L \in [-M,M]$. $\blacksquare$
I boxed the part I didn't understand. I don't understand how we know which interval has $\infty$-many values of n for $x_n$ to be in that interval. Take $(-1)^n$ for example, I feel like both intervals $[-1,0]$ and $[0,1]$ have $\infty$-many values of $n$ such that $x_n$ are in the intervals, i.e., $1 \in [0,1]$ and $-1 \in [-1,0]$. Aren't both even numbers and odd numbers of $n$ be infinitely many in $\mathbb{N}$? Since $\mathbb{N}$ is $\infty$-many, how can we extract one set with $\infty$-many and another with finitely many numbers? I just can't convince myself to accept this part.
Best Answer
The proof doesn't assume that one of the half-intervals has infinitely many terms while the other has finitely many terms; it only says that at least one of the halves has infinitely many terms, and one can be chosen arbitrarily. In fact, if $[a_n,\frac{a_n+b_n}{2}]$ and $[\frac{a_n+b_n}{2},b_n]$ both have infinitely many terms, the process used in the proof may be applied to both intervals, and thus there are at least two subsequences converging to different values. This is the case for your example of $(-1)^n$, since there are subsequences converging to both $1$ and $-1$.