How to reconcile the existence of the least upper bound? 
A set of reals that is bounded above has the least upper bound.

It is not intuitively clear to me that it should be true. I am aware of constructions of the reals from rationals where this statement is proved as a theorem, but they justify it logically and don't help my intuition. So I am looking for intuition in order to reconcile this statement to myself.
That best I could come up with is this: let $a$ be a rational number that is always greater than any element of the set and rational number $b$ is always smaller than some element of the set. Using a method like bisection search we can make the distance between $a$ and $b$ as small as we like and by that "compute" the least upper bound with any precision. I visualize the least upper bound as a decimal number, and it is clear to my intuition that If I can compute as many digits after the point as I wish for this number, this number must exist.
But the problem is that I heard of real numbers that are not computable, and if this number is in the set at hand, I will not be able to approximate the least upper bound, but the axiom that it exists still applies (I guess).
 A: Well, let's suppose $S$ is a non-empty set of real numbers that is bounded above, and see what it would mean if there weren't a least upper bound of $S$ in $\Bbb R.$ Let's not worry too much about which construction of $\Bbb R$ we're working with, and just stick to the intuitive idea of a "number line." We'll interpret $<$ to mean "lies to the left of" and $\le$ to mean "doesn't lie to the right of." So, "least" means leftmost, and $x$ being an "upper bound" of a set $S$ means no point of $S$ lies to the right of $x.$
Let $B$ be the set of upper bounds of $S,$ i.e.: $B=\bigl\{b\in\Bbb R:\forall s\in S(s\le b)\bigr\}.$ Note that $B$ is non-empty since $S$ is bounded above, and $B$ is bounded below since $S$ is non-empty. Further note that $B$ is a real interval--in the sense that, given two distinct points of $B,$ every point lying between them is also a point of $B$ (since lying between two points of $B$ implies lying to the right of a point of $B,$ which implies lying to the right of every point of $S$). Consequently, $B$ has no "gaps" in it.
Moreover, note that $B$ has no upper bound. Indeed, if no point of $B$ lies to the right of $y,$ then there is some $b\in B$ lying no further to the right than $y$ (since $B$ is non-empty). Since $y+1$ lies to the right of $y,$ then $y+1$ also lies to the right of $b.$ Since, $b\in B,$ then no point of $S$ lies to the right of $b,$ so no point of $S$ lies to the right of $y+1,$ and so $y+1\in B$ by definition. But we assumed that no point of $B$ lies to the right of $y,$ and concluded that $y+1$ is a point of $B$ lying to the right of $y,$ which is absurd. Consequently, if we go far enough to the right on the number line, we will eventually encounter only points of $B$ as we continue to the right.
Since $B$ is a real interval with a lower bound and no upper bound, then intuitively*, it has the form $[a,\infty)$ or $(a,\infty)$ for some $a\in\Bbb R.$ If the former, then $a$ is the least upper bound of $S,$ so let's suppose the latter, to see what goes wrong.
Well, first, note that $a,$ above, is unique. Indeed, if $B=(a',\infty),$ then $(a',\infty)\subseteq(a,\infty)$ means that every number to the right of $a'$ is also to the right of $a,$ so in particular, $a'$ doesn't lie to the right of $a.$ But similarly, $a$ doesn't lie to the right of $a',$ so $a'=a.$
So, since $B=(a,\infty),$ then the points lying to the right of $a$ are exactly the points of $B.$ Since $a$ is not a point of $B,$ then by definition of $B,$ there is some $s\in S$ lying to the right of $a,$ and so their midpoint (say $m$) lies to the right of $a,$ while $s$ lies to the right of $m.$ But this is a problem! On the one hand, since there is a point of $S$ lying to the right of $m,$ then $m$ is not a point in $B$ by definition of $B.$ But on the other hand, $m$ lies to the right of $a,$ so $m$ is a point of $(a,\infty)=B.$

*Obviously, if this isn't intuitive for you, then my answer may not be enough, on its own. Still, it gives a more visualizable approach (in terms of intervals on a line) than the more formal approach that has stymied you.


Added: Let me give that "intuitive" leap more justification--it's rather wanting of it. To that end, let's consider the set $L$ of lower bounds of $B$--that is, the set of points $x$ such that no point of $B$ lies to the left of $x.$ By definition of $B,$ given any $s\in S,$ no point of $B$ lies to the left of $s.$ Thus, every point of $S$ is a point of $L.$ Consequently, any upper bound of $L$ will be an upper bound of $S,$ so $B$ contains every upper bound of $L.$ On the other hand, given any $b\in B,$ we have that no point of $L$ lies to the right of $b$ (for then $b$ would lie to the left of said point of $L$), and so $B$ is exactly the set of upper bounds of $L.$
By similar approaches to the work we did before, we find that $L$ is a non-empty real interval that is bounded above, but not bounded below. Note that if $L$ has a rightmost point, then it is the leftmost point of $B.$ If $B$ has a leftmost point, then that point is precisely the least upper bound of $S$ (if it exists). At this point, let's use the set $L$ and take a different approach.
I define the midpoint function by $m(x,y):=\frac12(x+y).$ Readily, if $x<y,$ then $x<m(x,y)<y$ and $m(x,y)-x=y-m(x,y)=\frac12(y-x).$
We now define two (possibly finite) sequences of numbers, and use them to help ourselves visualize the relationship between $L$ and $B$. (This will be quite similar to the approach you suggested.)
Take any $l_0\in L$ and any $b_0\in B.$ Let's imagine that all the points of the number line start out black. Then, we "paint" all points to the left of $l_0$ on the number line lemon yellow and all points to the right of $b_0$ on the number line berry blue. Now, it should be clear that every yellow point is a point of $L,$ every blue point is a point of $B,$ and the black points comprise the closed interval from $l_0$ to $b_0,$ which has length $b_0-l_0.$ Now, if $l_0$ is to the right of all other points of $L,$ or if $b_0$ is to the left of all other points of $B,$ then we have found the least upper bound of $S.$ Suppose not.
Suppose that we have points $l_k\in L$ and $b_k\in B$ for some non-negative integer $k,$ such that the following hold:


*

*there are points of $L$ to the right of $l_k,$

*there are points of $B$ to the left of $b_k,$

*we have already painted all points to the left of $l_k$ yellow,

*we have already painted all points to the right of $b_k$ blue,

*all yellow points are points in $L,$

*all blue points are points in $B,$ and

*the points from $l_k$ to $b_k$ comprise a closed interval of length $2^{-k}(b_0-l_0)$ consisting entirely of black points.


Consider $m(l_k,b_k).$ If $m(l_k,b_k)$ is the leftmost point of $L$ or (equivalently) the rightmost point of $B,$ then we've found our least upper bound of $S$ and we're done. Suppose not, so that $m(l_k,b_k)$ cannot belong to both $L$ and $B.$ In fact, $m(l_k,b_k)$ must lie in $L$ or $B.$ After all, if it doesn't lie in $B,$ then it can't lie to the right of any element of $B,$ so lies in $L$ by definition!
If $m(l_k,b_k)$ is a point of $L$ only, then let $l_{k+1}=m(l_k,b_k)$ and $r_{k+1}=r_k.$ If $m(l_k,b_k)$ is a point of $B$ only, then let $l_{k+1}=l_k$ and $b_{k+1}=m(l_k,b_k).$ In either of these two cases, "paint" all points to the left of $l_{k+1}$ lemon yellow and all points to the right of $b_{k+1}$ berry blue, so we have the following:


*

*there are points of $L$ to the right of $l_{k+1},$

*there are points of $B$ to the left of $b_{k+1},$

*we have already painted all points to the left of $l_{k+1}$ yellow,

*we have already painted all points to the right of $b_{k+1}$ blue,

*all yellow points are points in $L,$

*all blue points are points in $B,$ and

*the points from $l_{k+1}$ to $b_{k+1}$ comprise a closed interval of length $2^{-(k+1)}(b_0-l_0)$ consisting entirely of black points.


In this fashion, we have recursively defined the sequences.
Assuming that the recursion doesn't halt (that is, that none of the $l_k$s or $b_k$s is the desired least upper bound of $S$), then at every stage, we paint more of the points of $L$ yellow or more of the points of $B$ blue. Moreover, the length of the interval of black points is positive at every stage, but continues to shrink, and given any positive length, the interval of black points will eventually be smaller than that length. Intuitively, after "completing the recursion," the interval of black points will comprise a closed interval of length $0$--that is, there will be only a single black point! Moreover, every point to the right of it will be blue, and every point to the left of it will be yellow, so that the black point is an upper bound of $L,$ so an upper bound of $S,$ and so is a point of $B,$ necessarily the least such. Again, we're done.
A: Take the set of real number, which is built up or with Dedekind's cut as @Arthur said, or with an axiomatic approach which involves an axiom called "Nested Intervals Axiom". 
This is the intuition: If I take an interval $[a,b]$ and then from it I built another interval nested with the first $[a_1,b_1]$ and from this I repeat the construction, then if I take the intersection of all this nested intervals indexed on all natural numbers, then I find only one real number in the intersection.
Once thought at this the proof of the existence of least upper bound is almost done, because you have to built a succession of nested intervals starting with a point that is not a majorant and a point that is. 
A: This approach treats the reals as defined by Cauchy sequences of rational numbers. We understand "upper bound", "decreasing", etc. in the inclusive sense ($\geqslant$ rather than $>$). Let $a_0$ be any rational number that is not an upper bound for the set $S$, and $a_1$ a rational upper bound for $S$. Let $a_2=\frac12(a_0+a_1)$. If $a_2$ is an upper bound for $S$, then choose $a_3=\frac12(a_0+a_2)$; otherwise choose $a_3=\frac12(a_1+a_2)$. Continue like this so that, given $a_0,\ldots,a_k$, the point $a_{k+1}$ is the average of the least of the $a_0,\ldots,a_k$ that is an upper bound for $S$ and greatest of those that are not. It is straightforward to verify that this sequence satisfies $|a_{n+1}-a_n|\leqslant2^{-n}(a_1-a_0)$ ($n\in\Bbb N$). Consider the series $$\sum_{k=0}^{m+n}(a_{k+1}-a_k)=\sum_{k=0}^{m}(a_{k+1}-a_k)+\sum_{k=m+1}^{m+n}(a_{k+1}-a_k).$$We can place an upper bound $2^{-m}(a_1-a_0)$ on the magnitude of the "tail" $\sum_{k=m+1}^{m+n}(a_{k+1}-a_k)$ which, by telescoping the other series in the equation, shows that $|a_{m+n}-a_{m+1}|\leqslant2^{-m}(a_1-a_0)$ ($m,n\in\Bbb N)$. So $(a_k:k\in\Bbb N)$ is a Cauchy sequence which therefore has a limit $a$. By partitioning the sequence into the decreasing (possibly finite) sub-sequence of upper bounds and the increasing sequence of non-upper-bounds, it can be seen that there can neither be $s\in S$ with $s>a$ nor any upper bound $b$ for $S$ such that $b<a$. It follows that $a$ is the least upper bound for $S$.
